各种排序方法的比较与讨论.doc

各种排序方法的比较与讨论现在流行的排序有：选择排序、直接插入排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序。一、选择排序1 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2. 排序过程：【示例】： 初始关键字 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 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序结果 13 27 38 49 49 76 76 973.void selectionSort(Type* arr,long len) long i=0,j=0;/*iterator value*/ long maxPos; assertF(arr!=NULL,In InsertSort sort,arr is NULLn); for(i=len-1;i=1;i-) maxPos=i; for(j=0;j if(arrmaxPos if(maxPos!=i)swapArrData(arr,maxPos,i); 选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.二.直接插入排序插入排序（Insertion Sort）的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。直接插入排序直接插入排序（Straight Insertion Sort）：将一个记录插入到排好序的有序表中，从而得到一个新的、记录数增1的有序表。 直接插入排序算法哨兵（监视哨）有两个作用：一是作为临变量存放Ri（当前要进行比较的关键字）的副本；二是在查找循环中用来监视下标变量j是否越界。 当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)。算法的辅助空间复杂度是O(1)，是一个就地排序。 直接插入排序是稳定的排序方法。三. 冒泡排序算法思想：将被排序的记录数组R1.n垂直排列，每个记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 算法： void BubbleSort(SeqList R) /R（l.n)是待排序的文件，采用自下向上扫描，对R做冒泡排序 int i，j； Boolean exchange； /交换标志 for(i=1;i exchange=FALSE； /本趟排序开始前，交换标志应为假 for(j=n-1;j=i；j-) /对当前无序区Ri.n自下向上扫描 if(Rj+1.key R0=Rj+1； /R0不是哨兵，仅做暂存单元 Rj+1=Rj； Rj=R0； exchange=TRUE； /发生了交换，故将交换标志置为真 if(!exchange) return；/本趟排序未发生交换，提前终止算法 /endfor(外循环) /BubbleSort 分析：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。 算法思想：将被排序的记录数组R1.n垂直排列，每个记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 算法： void BubbleSort(SeqList R) /R（l.n)是待排序的文件，采用自下向上扫描，对R做冒泡排序 int i，j； Boolean exchange； /交换标志 for(i=1;i exchange=FALSE； /本趟排序开始前，交换标志应为假 for(j=n-1;j=i；j-) /对当前无序区Ri.n自下向上扫描 if(Rj+1.key R0=Rj+1； /R0不是哨兵，仅做暂存单元 Rj+1=Rj； Rj=R0； exchange=TRUE； /发生了交换，故将交换标志置为真 if(!exchange) return；/本趟排序未发生交换，提前终止算法 /endfor(外循环) /BubbleSort 分析：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。四. 希尔排序基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2 该方法实质上是一种分组插入方法。给定实例的shell排序的排序过程 假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次为： 5，3，1Shell排序的算法实现1 不设监视哨的算法描述void ShellPass(SeqList R，int d) /希尔排序中的一趟排序，d为当前增量 for(i=d+1;i0&R0.key Rj+d=R0； /插入Ri到正确的位置上 /endif /ShellPassvoid ShellSort(SeqList R) int increment=n； /增量初值，不妨设n0 do increment=increment/3+1； /求下一增量 ShellPass(R，increment)； /一趟增量为increment的Shell插入排序 while(increment1) /ShellSort注意： 当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件j0，以防下标越界。2设监视哨的shell排序算法算法分析1增量序列的选择 Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征： 最后一个增量必须为1； 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。2Shell排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因：当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。3稳定性 希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。五. 堆排序1、 堆排序定义 n个关键字序列Kl，K2，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1) kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i ) 若将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。2、大根堆和小根堆 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。注意： 堆中任一子树亦是堆。 以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。3、堆排序特点 堆排序(HeapSort)是一树形选择排序。 堆排序的特点是：在排序过程中，将Rl.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。4、堆排序与直接插入排序的区别 直接选择排序中，为了从R1.n中选出关键字最小的记录，必须进行n-1次比较，然后在R2.n中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。 堆排序可通过树形结构保存部分比较结果，可减少比较次数。5、堆排序 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。（1）用大根堆排序的基本思想 先将初始文件R1.n建成一个大根堆，此堆为初始的无序区 再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key 由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1.n-2.keysRn-1.n.keys，同样要将R1.n-2调整为堆。 直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作： 初始化操作：将R1.n构造为初始堆； 每一趟排序的基本操作：将当前无序区的堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。注意：只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。（3）堆排序的算法：void HeapSort(SeqIAst R) /对R1.n进行堆排序，不妨用R0做暂存单元 int i； BuildHeap(R)； /将R1-n建成初始堆 for(i=n;i1；i-) /对当前无序区R1.i进行堆排序，共做n-1趟。 R0=R1；R1=Ri;Ri=R0； /将堆顶和堆中最后一个记录交换 Heapify(R，1，i-1)； /将R1.i-1重新调整为堆，仅有R1可能违反堆性质 /endfor /HeapSort各种排序方法的选择选择合适的排序方法应考虑的因素： 待排序的记录数目n； 记录的大小（规模）； 的结构及其初始状态； 对稳定性的要求； 语言工具的条件； 结构； 时间和辅助空间复杂度等。 各种排序方法的选择 就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当n较大时，归并排序较堆排序省，但归并排序所需的辅助空间最大。 简单排序方法中，直接插入排序最简单，当待排序的结点已按键值“基本有序”且n较小时，则应采用直接插入排序或冒泡排序，直接插入排序比冒泡排序更快些，因此经常将直接插入排序和其他的排序方法结合在一起使用。 当n很大且键值位数较小时，采用基数排序较好；而当键值的最高位分布较均匀时，可先按其最高位将待排序结点分成若干子表，而后对各子表进行直接插入排序。 从方法的稳定性来比较，直接插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法；而直接选择排序、希尔排序、堆排序和快速排序都是不稳定的排序方法。 我们从以下几个方面对本章介绍过得内排序方法进行比较：（1）时间复杂性，（2）空间复杂性，（3）稳定性。三种简单的排序方法：直接插入、直接选择、冒泡排序时间复杂性均为O（n2）。堆排序、快速排序和归并排序这三种排序方法的平均情况的时间复杂性是O(nlogn)。希尔排序介于O（n2）与O(nlogn)之间。但在最坏情况下，快速排序的时间复杂性为O（n2）。最坏情况对其它排序方法影响不大。从空间复杂性看，归并排序的空间复杂性为O(n)。快速排序的空间复杂性为O(logn)，但快速排序在最坏情况下的空间复杂性为O（n）。其它排序方法的空间复杂性为O(1)。各种排序方法中，直接插入、冒泡和归并排序是稳定的，直接选择、快速排序和堆排序是不稳定的。除了基数排序以外，本章介绍的所有的排序算法都决定于两个关键字的直接比较。例如，冒泡排序不断地比较相邻记录的关键字值，直到升到正确的位置。相反地，基数排序并没有直接比较关键字的值，而是取决于关键字值中各位数字的值。实验数据表明，基于比较的排序算法是较好的。对于任何基于