数学和计算机科学板块_辛酸网

数据结构与算法19

  希尔排序是一种大量分组逐渐减小距离增量的排序算法：首先对于长度为n的整体序列，设置n/2的距离增量。 （从0开始）第0个元素和第$\frac{\mathrm{n}}{2}$个比较，第1个元素和第$\frac{\mathrm{n}}{2}+1$个比较， 第2个元素和第$\frac{\mathrm{n}}{2}+3$个比较，第3个元素和第$\frac{\mathrm{n}}{2}+3$个比较…… 第$\frac{\mathrm{n}}{2}$个元素和第n个比较。就这样，整个序列分为$\frac{\mathrm{n}}{2}$个分组。 在每个分组内部分别进行插入排序。这样经过一轮后，整体的有序性得到增加。

  下一步，减小距离增量，每一轮将距离增量减半，每一分组内继续插入排序，直到距离增量为1时，排序结束。 对前文那个乱序的数列分组及其交换过程如下：

  希尔排序内部是包含了插入排序的。所以也有人叫插入排序为直接插入排序，管希尔排序叫希尔插入排序。

  桶排序和睡眠排序一样是特殊的排序——其排序过程不依赖于元素之间的比较。桶排序的最简单形式是计数排序。 对于n个元素，我们事先搞清楚其中的取值范围是a~b，然后设立(b-a+1)个桶，编号也就是a~b。遍历整个序列，对于其中的一个元素x，当它的取值为m时，就把这个元素放在m号桶里面。 这样一来，在遍历了整个序列后，数量多的那个取值对应的桶里面元素就多。现在我们从a号桶开始到b号桶，遍历每一个桶，把其中的元素一个个再拿出来。 从前往后拿出来的顺序就是从小到大的顺序。如果被排序的元素仅仅是数字，那么一个桶就仅仅是一个记录了该编号的数有几个的计数工具，所以这种方法叫做计数排序。 对于n个元素，当取值范围有k个值时，计数排序就是遍历n个元素放桶里，遍历k个桶拿出来，时间复杂度O(n+k)。   请看这巧妙的代码：

int countsort(int a[],int length,int min,int max)//C99之前的C语言标准不支持变量作为数组长度
{//C98标准下请用define预处理指令预先定死取值范围
	int bucket[max-min+1];for(int i=0;i<max-main+1;i++)bucket[i]=0;//初始化桶
	for(int i=0;i<length;i++)bucket[a[i]]++;//把值为a[i]的数放在编号为a[i]的桶里，a[i]号桶内元素数量加1
	int result[length];int n=0;
	for(int i=0;i<max-main+1;i++)//根据桶的编号将其内元素逐个拿出
		for(int j=0;j<bucket[i];j++){result[n]=bucket[i];n+=1;}
	return result[];
}

  计数排序有一个非常严重的局限性：单纯对桶编号的话，就要求被排序元素的关键字取值范围是离散的。 不过用Python字典或C++STLmap的话倒是能做到对连续取值的计数排序。再推广一下，如果每个桶的取值范围不单身一个数而是一个连续的区间呢？ 例如被排序元素取值范围1~100，我们不设置100个桶而是10个桶，1号桶内范围[1,10)，2号桶范围[10,20)……10号桶则为[90,100]，这样在一开始入桶操作中， 关键字在哪个范围就放哪个桶内。下一步，对每一个桶进行内部排序，内部排序可以用插入、选择等各种办法。最后每一个桶里的元素按照大小逐个输出即可。 对于n个元素和m个桶，当桶内排序最快为O(logk)的时间复杂度时，桶排序整体的时间复杂度为$\mathrm{O(nlog}\frac{\mathrm{n}}{\mathrm{m}}\mathrm{)}$， 在数据分布不是很均匀的情况下很有可能退化为O(n²)。

  桶排序的稳定性和桶内的处理方式有关，如果桶内是队列，则依旧稳定。

  已知有A,B,C,3个柱子和n个圆盘，圆盘从上到下依次增大，这n个圆盘都在柱子A上。要求：将所有圆盘以原有的从上到下依次增大的顺序， 出现在另一个柱子上。每次只能移动柱子上最上面的一个圆盘，且必须是小圆盘在大圆盘之上，或是放在空柱子上。先放在柱子上的圆盘在底部。问：所有的圆盘从A到C一共要移动多少次？

  因为一开始大圆盘在小圆盘下面，要把小圆盘放在终点柱子上就得先把大圆盘放在终点柱子上，但这被小圆盘挡住了。 所以要先把小圆盘放在中间柱子上，再把大圆盘放在终点柱子上，最后小圆盘移动到终点柱子上。递归地说，将n个圆盘从起始柱子，经过中间柱子到终点柱子有下列步骤：
  ①把1~n-1号圆盘整体放在中间柱子上；
  ②把n号圆盘放在终点柱子上；
  ③把1~n-1号圆盘整体放在终点柱子上。

  以8块圆盘为例，上代码：

int number=0;//搬运次数
int hanoi(int n,char start,char middle,char end)
{//参数依次为：圆盘数量，起始柱子编号，中间柱子编号，终点柱子编号
	if(n==1){//递归奠基，1快直接搬
		printf("%c to %c",start,end);number=1;
	}else if(n==2){//递归奠基，搬3次
		printf("%c to %c",start,middle);printf("%c to %c",start,end);printf("%c to %c",middle,end);
		number=3;
	}else{
		hanoi(n-1,start,end,middle);//第一步，前面的放在中间柱子上
		printf("%c to %c",start,end);number+=1;//第二步，次数加1
		hanoi(n-1,middle,start,end);//第三步，前面的转移到终点柱子上
	}
}
hanoi(8,'A','B','C');
printf("number=%d",number);//输出次数

  据说n块要搬2ⁿ-1次，64块圆盘要好多亿年

  分治，分而治之，把大问题分成小问题，一般来说都是递归地分解想下去。对子问题求解。然后回溯地将子问题的解合并为大问题的解。 递归树中左边的代价就是分代价，即子问题求解代价之和，右边为治代价，也就是子问题解合并为大问题的解要用的代价。

  我们知道，按照定义而算的话矩阵乘法的时间复杂度就是O(n³)。对于两个2阶方阵而言，在矩阵乘法中， 我们考察其中的元素运算——一共8次乘法和4次加法。众所周知，计算机算乘法要慢过加法，从逻辑门的层数就容易看到了，这时间差距根本就不是一个数量级的。 除法更是慢的要死，而减法则和加法几乎一致。所以在大量线性运算中科学家们希望计算机多去做加减法，少做乘除法。斯特森矩阵乘法在运算中共有7次乘法和18次加法， 正因为乘法少了一次而加法多出的时间比不上这个数量级，所以更快。

  设有矩阵A= $\left[\begin{array}{cc}{\mathrm{a}}_{11}& {\mathrm{a}}_{12}\\ {\mathrm{a}}_{21}& {\mathrm{a}}_{22}\end{array}\right]$ B=$\left[\begin{array}{cc}{\mathrm{b}}_{11}& {\mathrm{b}}_{12}\\ {\mathrm{b}}_{21}& {\mathrm{b}}_{22}\end{array}\right]$， 求C=$\left[\begin{array}{cc}{\mathrm{c}}_{11}& {\mathrm{c}}_{12}\\ {\mathrm{c}}_{21}& {\mathrm{c}}_{22}\end{array}\right]$， 今有中间值M₁~M₇如下:

  然后矩阵C就是：

  如果A和B是很大的而非2×2的矩阵，则采取分块矩阵的方式，表达式中的加法和乘法也就是矩阵加法与乘法。 而在表达式中的矩阵乘法，还可以再进一步进行分块，就此，用分治的方式解决了问题。斯特森矩阵乘法的时间复杂度是O(n^log7)≈O(n^2.81)。

辛酸网 ©版权所有