内部算法性能分析 第4章 详细设计
{R1,R4,R7,R10},{R2,R5,R8}和{R3,R6,R9}进行直接插入排序，其结果如第二趟排序所示，最后对整个序列进行一趟直接插入排序。至此，希尔排序结束，整个序列的记录已按关键字非递减有序排列，如下图4.2所示：
【初始关键字】：49 38 65 97 76 13 49 55 04
49
38
13
27
49 65 97
76
55 04
一趟排序结果：13 27 49 55 04 49 38 65 97 76 13 55 38 76 27 04 65 49 49 97
二趟排序结果：13 04 49 38 27 49 55 65 97 76 三趟排序结果：04 13 27 38 49 49 55 65 76 97
图4.2希尔排序过程
从上述排序过程可见，希尔排序的一个特点是：子序列的构成不是简单地“逐段分割”而是将相隔某个“增量”的记录组成一个子序列。如上例中，第一趟排序时的增量为5，第二趟排序时的增量为3，第三趟排序时的增量为1，由于在前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键进行比较，到越后面排序的数变得越来越有序，为此算法如下：
for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区 if(R[ i ].key R[0]=R[i];j=i-d； //R[0]只是暂存单元，不是哨兵 do { //查找R的插入位置 R[j+d]=R[j]； //后移记录 j=j-d； //查找前一记录 }while(j>0&&R[0].key R[j+d]=R[0]； ｝ //插入R到正确的位置上 算法优劣：不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是 12 内部算法性能分析 第4章 详细设计 基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logn)2)， 没有快速排序算法快 O(n*(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是 最优选择。但是比O(n2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。 专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。 当N值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。 稳定性：希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。 4.4简单选择排序 一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+j个记录中选出关键字最小的记录，并和第i（1 N个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： 初始状态：无序区为R[1..n]，有序区为空。 第1趟排序,在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 第i趟排序,第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 for(i=1;i<=L;i++) 13 内部算法性能分析 第4章 详细设计 { n=i; for(j=i+1;j<=L;j++) { times++; h=j; if(h!=j) changes+=3; } } if (R[j] { R[0]=R[h];R[h]=R[i];R[i]=R[0]; 数据排序过程： 初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 [38 65 97 76 49 27 49] 第二趟排序后 13 27 [65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [76 97 65 49 ] 第五趟排序后 13 27 38 49 49 [97 65 76] 第六趟排序后 13 27 38 49 49 65 [97 76] 第七趟排序后 13 27 38 49 49 65 76 [97] 最后排序结果 13 27 38 49 49 65 76 97 从上述可见，算法的结构是一个双重循环。假设共有N个数据，则内循环体的总数执行次数为：N（N-1）=N*N/2，移动次数为(n+4)(n-1)/2，因此时间复杂 O(n*n)，内循环体为一判断语句，需要比较两个关键字的大小，并且在满足条件 时要执行交换过程。选择排序算法只需要有限的几个辅助内存且与线性中元素的个数N无关，因此，算法的空间复杂性是常数级的，即O（1）。 4.5快速排序 快速排序（Quicksort）是对冒泡排序的一种改进。最有效、从而最广泛使用的排序算法之一是由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 其算法如下： 设置两个变量i、j，排序开始的时候：i=0，j=n-1； 以第一个数组元素作为关键数据，赋值给key，即 key=A[0]； 从j开始向前搜索，即由后开始向前搜索（j=j-1），找到第一个小于key的值A[j]，并与key交换； 从i开始向后搜索，即由前开始向后搜索（i=i+1），找到第一个大于key的 14 内部算法性能分析 第4章 详细设计 A[i]，与key交换； 重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。) 例如：待排序的数组A的值分别是：（初始关键数据：X=49） 注意关键X永远不变，永远是和X进行比较，无论在什么位子，最后的目的就是把X放在中间，小的放前面大的放后面如4.2所示： 初始关键字： 49 38 65 97 76 13 27 49 i j j 进行1次交换之后：27 38 65 97 76 13 49 i i j 进行2次交换之后：27 38 97 76 13 65 49 i j j 进行3次交换之后：27 38 13 97 76 65 49 i i j 进行4次交换之后：27 38 13 76 97 65 49 i j j 完成一趟排序： 27 38 13 49 76 97 65 49 有序序列 ｛13 27 38 49 49 65 76 97｝ 图4.3快速排序过程 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。 在最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大) 的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：Cmax = n(n-1)/2=O(n2) 然而在最好情况下，每次划分所取的基准都是当前无序区的\中值\记录，划 分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：0(nlgn) 在当前无序区中选取划分的基准关键字是决定算法性能的关键，如下所示： \三者取中\规则，即在当前区间里，将该区间首、尾和中间位置上的关键字 比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的Partition算法完全相同。 15 内部算法性能分析 第4章 详细设计 取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准。 选取基准最好的方法是用一个随机函数产生一个取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准，这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。 注意：随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数据随机分布的算法。 尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。 4.6堆排序 堆排序(Heap Sort) 是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 排序之前首先建堆，堆的定义如下：n个元素的序列｛k1,k2??，kn｝当且仅当满足下关系时，称之为堆。 若将和此序列对应的一维数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中年有非终端结点的值均不大于或不小于其左、右孩子结点的值。由此,若序列｛k1,k2,??，kn｝是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值或（或最大值）下列两个序列为堆，对应的完全二叉树如图4.3所示： 9239152384361407258790443152 图4.4（A）堆元素最大 （ b）堆元素最小 大根堆排序的基本思想 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区 16