常用排序算法总结 - iamfranter的专栏 - 博客频道 - CSDN.pdf

2014年5月6日 常用排序算法总结 - iamfranter的专栏 - 博客频道 - CSDN.NET 1/11常用排序算法总结所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的要注意的是，排序算法的稳定性是针对所有输入实例而言的即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的一.插入排序插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止插入排序方法主要有直接插入排序和希尔排序①.直接插入排序(稳定)接插入排序的过程为：在插入第i个记录时，R1,R2,..Ri-1已经排好序，将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较，找到适当的位置使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。

代码如下:1. void Dir_Insert(int A[],int N) 2. { 3. int j,t; 4. for(int i=1;it) 9. { 10. A[j+1]=A[j]; 11. j--; 12. } 13. A[j+1]=t; 14. } 15. } ②.希尔排序(不稳定)：希尔(Shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组所有距离为d1的倍数的记录放在同一个组中先在各组内进行直接插入排序；然后，取得第二个增量d2 0) 6. { 7. for(j=k;j=0 && A[i]>t) 12. { 13. A[i+k]=A[i]; 14. i=i-k; 15. } 16. A[i+k]=t; 17. } 18. if(k == 1) break; 19. (k/2)%2 ==0 ? k=k/2+1 : k=k/2; 20. } 21. } 二.选择排序选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完选择排序中主要使用直接选择排序和堆排序。

①.直接选择排序(不稳定)直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换......依次类推，直到所有记录排完为止无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较，因此，总的比较次数为n(n-1)/2=O(n^2)当初始文件为正序时，移动次数为0；文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)直接选择排序的平均时间复杂度为O(n^2)直接选择排序是不稳定的2014年5月6日 常用排序算法总结 - iamfranter的专栏 - 博客频道 - CSDN.NET 3/11代码如下:1. void Dir_Choose(int A[],int n) 2. { 3. int k,t; 4. for(int i=0;i=K2i且Ki>=K2i+1),(1k2，则交换k1和k2所在的记录，否则不交换继续对k2和k3重复上述过程，直到处理完kn-1和kn这时最大的排序码记录转到了最后位置，称第1次起泡，共执行n-1次比较与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行n-2次比较。

依次类推，共做n-1次起泡，完成整个排序过程若文件的初始状态是正序的，一趟扫描即可完成排序所需关键字比较次数为n-1次，记录移动次数为0因此，冒泡排序最好的时间复杂度为O(n)若初始文件是反序的，需要进行n-1趟排序每趟排序要进行n-i次关键字的比较(1=t) h--; 11. if(h>l) 12. { 13. temp=A[l]; 14. A[l]=A[h]; 15. A[h]=temp; 16. } 17. } 18. Quick_Sort(A,low,l-1); 19. Quick_Sort(A,l+1,high); 20. } 21. } 四.归并排序归并排序是将两个或两个以上的有序子表合并成一个新的有序表初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并直到得到长度为n的有序表，排序结束归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现，对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。

归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为O(n),显然它不是就地排序1. void merge(int *array, int *temp_array, int left, int right, int right_end) 2. { 3. int left_end = right - 1, i; 4. int tmp = left; 2014年5月6日 常用排序算法总结 - iamfranter的专栏 - 博客频道 - CSDN.NET 7/114. int tmp = left; 5. int num = right_end - left+1; 6. 7. while (left a[center_index]如果i和j都走不动了，i j 交换a[j]和a[center_index]，完成一趟快速排序在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。

5)归并排序归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序2014年5月6日 常用排序算法总结 - iamfranter的专栏 - 博客频道 - CSDN.NET 11/11列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性所以，归并排序也是稳定的排序算法6)基数排序基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前基数排序基于分别排序，分别收集，所以其是稳定的排序算法7)希尔排序(shell)希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。

所以，希尔排序的时间复杂度会比o(n^2)好一些由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的8)堆排序我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性但当为n /2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了所以，堆排序不是稳定的排序算法QR Codeh t t p : / / b l o g . c s d n . n e t / i a m f r a n t e r / a r t i c l e / d e t a i l s / 6 8 2 5 2 0 7h t t p : / / g o o . g l / f f g S。