排序算法总结

1 / 49 排序算法总结 各种排序算法的总结和比较 1 快速排序 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 如果不多于 1个数据，直接返回。 一般选择序列最左边的值作 为支点数据。 将序列分成 2部分，一部分都大于支点数据，另外一部分都小于支点数据。 对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而2 / 49 言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 2 归并排序 归并排序先分解要排序的序列，从 1 分成 2， 2分成 4，依次分解，当分解到只有 1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额 外的数组。 3 堆排序 堆排序适合于数据量非常大的场合。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所 有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建3 / 49 堆，交换数据，依次下去，就可以排序所有的数据。 Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是 O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用的分组方法。 Shell排序比冒泡排序快 5倍 ，比插入排序大致快 2倍。 Shell排序比起 QuickSort， MergeSort， HeapSort 慢很多。但是它相对比较简单，它适合于数据量在 5000 以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序 插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快 2 倍。一般不用在数据大于 1000 的场合下使用插入排序，或者重复排序超过 200数据项的序列。 冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较4 / 49 大的数据下沉，较小的数据上升。它是 O(n )的算法。 7 交换排序和选择排序 这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。 8 基数排序 基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮 点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事 情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。 9 总结 下面是一个总的表格，大致总结了我们常见的所有的排序算5 / 49 法的特点。 经典排序算法总结 -fly分享 目 录 /* 冒泡法 . 2 /* 快 速 排序 . 3 /* 插 入 排序 . 4 /* 希 尔 排序 . 5 /* 选择排序 .6 / 49 . 6 /* 堆排序 . 7 /* 归 并 排序 . 9 附： 排序算法原理： flash演示 : #include #include using namespace std; /* 冒泡法 左右元素相比，往后冒泡 7 / 49 */ template void BubbleSort(T* r, int n) T temp; int i,j; for (i=0;i for (j=0;j if (rj rj+1) temp = rj; 8 / 49 rj = rj+1; rj+1 = temp; 左边比他小，右边比他大，每次得到一个最左边数据的位置*/ template void QuickSort(T a,int low,int high) 9 / 49 if(low T elem = alow; int l = low, r = high; while(l while(l = elem) r-; if (l al+ = ar; while(l if (l ar- = al; 10 / 49 ar = elem; QuickSort(a,low,r-1); QuickSort(a,r+1,high); 向右移， aj+1=aj*/ template void insert_sort(T a,int n) int i,j; 11 / 49 T elem; for (i= 1;i j = i- 1; elem = ai; while(j=0 & elem aj+1 = aj; j-; aj+1 = elem; /*希尔排序 12 / 49 把插入排序的改成 d 即可 */ template void shell_insert(T array,int d,int len) int i,j; T elem; for ( i = d;i j = i - d; elem = arrayi; while (j = 0 & elem arrayj+d = arrayj; j = j - d; arrayj+d = elem; 13 / 49 template void shell_sort(T array,int len) int inc = len; do inc = inc/2; shell_insert(array,inc,len); while (inc 1); 14 / 49 现有序列 9,3,5,1,6,2,8,4,7，以此为例子，阐述各个常用排序算法。 直接插入排序： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。 第一趟比较前两个数 ,然后把第二个数按大小插入到有序表中 ; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了 (n-1)趟扫描以后就完成了整个排序过程。 直接插入排序属于稳定的排序，时间复杂性为 o(n )，空间复杂度为 O(1)。 9，3， 5， 1， 6， 2， 8， 4， 7 3， 9， 5， 1， 6， 2， 8， 4， 7 3， 5， 9， 1， 6， 2， 8， 4， 7 15 / 49 1， 3， 5， 9， 6， 2， 8， 4， 7 1， 3， 5， 6， 9， 2， 8， 4， 7 1， 2， 3， 5， 6， 9， 8， 4， 7 1， 2， 3， 5， 6， 8， 9， 4， 7 1， 2， 3， 4， 5， 6， 8， 9， 7 1， 2， 3， 4， 5， 6， 7， 8， 9 希尔排序： 先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1个组。所有距离为 dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 取增量为 5 则分为五个组，对这些分组内部进行插入排序， 得到： 2，3， 4， 1， 6， 8， 5， 7， 9 16 / 49 取增量为 3 则分为三个组 得到： 1， 3， 4， 2， 6， 8， 5， 7， 9 取增量为 1 得到 1， 2， 3， 4， 5， 6， 7， 8， 9 9， 3， 5， 1， 6， 2， 8， 4， 7 增量 5 对同一颜色进行内部插入排序 2， 3， 4， 1， 6， 8， 5， 7， 9 增量 3 1， 3， 4， 2， 6， 8， 5， 7， 9 增量 1 1， 2， 3， 4， 5， 6， 7， 8， 9 冒泡排序： 冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第 1 个和第 2 个数，将小数放前，大数放后。然后比较第 2 个数和第 3个数，将小17 / 49 数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较，将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到 一个新的最大数。如此下去，直至最终完成排序。 9， 3， 5， 1， 6， 2， 8， 4， 7 3， 5， 1， 6， 2， 8， 4， 7， 9 3， 1， 5， 2， 6， 4， 7， 8， 9 1， 3， 2， 5， 4， 6， 7， 8， 9 1， 2， 3， 4， 5， 6， 7， 8， 9 1， 2， 3， 4， 5， 6， 7， 8， 9 1， 2， 3， 4， 5， 6， 7， 8， 9 1， 2， 3， 4， 5， 6， 7， 8， 9 18 / 49 快速排序： 设要排序的数组是 A0AN -1，首先任意选取一个数据作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是： 1）设置两个变量 I、 J，排序开始的时候： I=1， J=N-1； 2）以第一个数组元素作为关键数据，赋值给 X，即 X=A0； 3）从 J 开始向前搜索，即由后开始向前搜索，找到第一个小于 X的值，让该值与 X 交换； 4）从 I 开始向后搜索，即由前开始向后搜索，找到第一个大于 X的值，让该值与 X 交换； 5）重复第 3、 4步，直到 I=J； 935162847 735162849 19 / 49 43516287 9 23516487 9 23416587 9 23146587 9 123 4 5687 9 123 4 5 6 78 9 123456789 归并排序： 归并排序是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组 A 有 N 个元素，那么可以看成数组 A是又 N 个有序的子序列组成，每个子序列的长度为 1，然后再两两合并，得到了一个 N/2 个长度为 2 或 1的有序子序列，再两两合并，如此重复，直到20 / 49 得到一个长度为 N 的有序数据序列为止，这种排序方法称为2 路合并排序。 9， 3， 5， 1， 6， 2， 8， 4， 7 3， 9， 1， 5， 2， 6， 4， 8， 7 1， 3， 5， 9， 2， 4， 6， 8， 7 两次合并后 1， 2， 3， 4， 5， 6， 8， 9， 7 第三次合并后 1， 2， 3， 4， 5， 6， 7， 8， 9 第四次合并后 选择排序： 每一趟从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最后， 直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果： 初始状态：无序区为 R1.n，有序区为空。 21 / 49 第 1趟排序 在无序区 R1.n中选出关键字最小的记录 Rk，将它与无序区的第 1 个记录 R1交换，使 R1.1和 R2.n分别变为记录个数增加 1个的新有序区和记录个数减少 1个的新无序区。 第 i趟排序 第 i 趟排序开始时，当前有序区和无序区分别为 R1.i-1和 R(1in -1)。该趟排序从当前无序区中选出关键字最小的记录 Rk，将它与无序区的第 1个记录 R交换，使 R1.i和 R分别变为记录个数增加 1个的新有序区和记录个数减少1 个的新无序区。 这样， n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。 9， 3， 5， 1， 6， 2， 8， 4， 7 第一次扫描， 1 最小，将 1与第一个数交换 1， 3， 5， 9， 6， 2，8， 4， 7 第二次扫描， 2最小，将 2 与第二个数交换 1， 2，22 / 49 5， 9， 6， 3， 8， 4， 7 1， 2， 3， 9， 6， 5， 8， 4， 7 1， 2， 3， 4， 6， 5， 8， 9， 7 1， 2， 3， 4， 5， 6， 8， 9， 7 1， 2， 3， 4， 5， 6， 7， 9， 8 1， 2， 3， 4， 5， 6， 7， 8， 9 第八次扫描， 8 最小，将 8 与第八个数交换 1， 2， 3， 4， 5， 6， 7， 8， 9 基数排序： 需而外构造十个数组或链表。对该例子进行一次分配就可排好。 实际应用中最常用的排序是快速排序和堆排序。所谓堆排序，就是将最小的一个值放到堆栈的顶部，这样就可以使最后出来的数完成排序。快速排序是不稳定的，堆排序是稳定的。所谓稳定，就是当两个值相等时，排序后两个值的顺序23 / 49 和排序前相同。以上两种排序使用的范围和情况是不同的，一般对于自然生成序列排序使用快速排序效率比较高，而对于已经有一定顺序的序列，使用堆排序比较合适，而且稳定的。 这里主要总结常用的 5种排序，分别是快速排序，冒泡排序，选择排序， shell 排序，插入排序。 下边分别介绍： 1 快速排序，就是从一个序列中随意取一个数，然后对剩下的数进行分类，小的放到左边，大的放到右边。如此进行下去知道最后。 N(n-1)/2.空间复杂度是 o. 2 冒泡排序，就是从 第一个数开始和后一个数比较，然后依情况交换，然后再用第二个和第三个比较交换，如此反复，直到最后一个。一直进行 n轮就可以完成排序。 3 选择排序，就是将一个序列中的最小的放到第一个，然后再将剩下的数据用相同的方式分别放到后一位。它的空间复杂度是 O(1). 24 / 49 4shell 排序，就是将有一定间隔的数进行排序，并且间隔变小，也就是开始是 n/2,然后继续变小，一般都是以一半为标准，直到最后间隔只有 1，也就完成了排序。需要的空间复杂度是 O(1). 5 插入排序，就比如平时玩的扑克排，一般整理排的时候需要将排排序，当你拿到一张新排的时候，就要比较左边和右边，只有在左右中间的那个值的时候才说明排序成功。它需要的空间复杂度也是 O(1). Ps:空间复杂度就是需要另外占用的空间。 以上排序中，只有快速排序是 O，其他都是 O，因为只有快速排序需要另外再起存储空间，而其他都是在原来空间中增加一个空间就可以。 1,快速排序 这个有点难解释 ,感觉上就是纽来纽去 ,先从首记录开始也行 ,从未记录开始也行 ,以后补上 . Tony Hoare 在 1962 年首次提出了快速 排序算法。对快速排25 / 49 序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序算法。只在输入数据项有更详细的信息时，其它排序算法才可能胜过快速排序算法。快速排序算法是利用分治技术的典型例子，随机分治策略是设计组合优化与计算几何一类问题有效算法的基础。分治策略分为三步： 将问题分成若干大小基本相 等的子问题； 独立地解决这些子问题； 将子问题归并成原问题的解。 快速排序的基本思路是：首先我们选择一个中间值 middle，把比中间值小的放在其左边，比中间值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架： void QuickSort(int *pData, int left, int right) int i, j; 26 / 49 int middle, iTemp; i = left; j = right; middle = pData(left + right) / 2; /求中间值 do while (pDatai while (pDataj middle) & (j left) /从右扫描小于中值的数 j-; if (i /交换 27 / 49 iTemp = pDatai; pDatai = pDataj; pDataj = iTemp; i+; j-; while (i / 当左边部分有值 (left if(left QuickSort (pData,left,j); /当右边部分有值 (righti)，递归右半边 if(righti) QuickSort (pData,i,right); 28 / 49 由此可见，上述排序算法中采用了递归策略。 在我设定的一个 10000 个无序记录集中 ,快速排序比冒炮节省了差不多一半时间 ,估计记录越多 ,这个数量级会更高 . 2,选择排序 , 选择排序和冒泡如果不仔细看 ,光从字面解释 ,很多人都弄混 ,解释这个很简单 ,举个例子就行 . 如 :2,6,1,4 首先将 2 和所有记录遍历 ,找出比他小的交换位置 ,于是 (第一个记录 ) 1,6,2,4 第二次 将 6 遍历 ,找出小的交换 (第二个记录 ) 29 / 49 1,2,6,4 第三次 . 1,2,4,6完成 ! 3,冒泡 这个就更加简单理解 两两相互之间比较 ,大 (或者小的 )放到前面 ,但必须遍历 N-1次 . 感觉上如果是无序的记录让他遍历效率会高 . 如 ,2,6,1,4 2,1,4,6(小的交换后继续和后面的记录交换 ) 1,2,4,6 完成 (N-1 次 ?好象是说选择排序了 ,忘记了 .) 30 / 49 数据量少的时候可以用冒泡 ,某些人说过冒泡效率最低 当然还有改良的冒泡双琏算法 . void CTestDlg:BubbleSort(int *pData,int iNum) /冒泡 int i,j; int temp; for(i=iNum-1;i0;i-) /iNum-1 次 for(j=0;j if(pDatajpDataj+1) temp =pDataj; 31 / 49 pDataj =pDataj+1; pDataj+1 =temp; 4 插入排序 将第一个记录看成已经排好的序列 ,其次数据一个一个与之前最大的记录比较 ,子 成序列 ,听说是如果有序的记录集合排序效果好 . void CTestDlg:insert_sort(int * list, int length) int i, j, temp; 32 / 49 for(i = 1; i temp = listi; j = i - 1; while(listj temp)&(j = 0) listj+1 = listj; j -; listj+1 = temp; / show_list(list, length); 33 / 49 各种排序算法的比较 XX-07-30 09:121.稳定性比较 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的 选择排序、希尔排序、快速排序、堆排序是不稳定的 2.时间复杂性比较 插入排序、冒泡排序、选择排序的时间复杂性为 O(n2) 其它非线形排序的时间复杂性为 O(nlog2n) 线形排序的时间复杂性为 O(n); 3.辅助空间的比较 线形排序、二路归并排序的辅助空间为 O(n),其它排序的辅助空间为 O(1); 34 / 49 4.其它比较 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。 反而在这种情况下，快速排序反而慢了。 当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。 若待排序的记录的关键字在一个明显有限范围内时 ,且空间允许是用桶排序。 当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。 当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。 当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序 35 / 49 1 快速排序 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 如果不多于 1个数据，直接返回。 shell排序 #include using namespace std; /* shell 排序是对插入排序的一个改装，它每次排序把序列的元素按照某个增量分成几个子序列，对这几 个子序列进行插入排序，然后不断的缩小增量扩大每个子序列的元素数量，直到增量为一的时候子序列 36 / 49 就和原先的待排列序列一样了，此时只需要做少量的比较和移动就可以完成对序列的排序了。 */ template void ShellSort(T array, int length) T temp; / 增量从数组长度的一半开始 ,每次减小一倍 for (int increment = length / 2; increment 0; increment /= 2) for (int indexI = increment; indexI 37 / 49 temp = arrayindexI; / 对一组增量为 increment 的元素进行插入排序 int indexJ; for (indexJ = indexI; indexJ = increment; indexJ -= increment) / 把 i之前大于 arrayi的数据向后移动 if (temp int main() int array6 = 2, 8, 6, 7, 5, 4; ShellSort(array, 6); for (int index = 0; index != 6; +index) cout 38 / 49 cout 插入排序 #include using namespace std; /* 插入排序是最简单最直观的排 序算法了，它的依据是：遍历到第 N个元素的时候前面的 N-1个元素已经是排 序好的了，那么就查找前面的 N-1 个元素把这第 N 个元素放在合适的位置，如此下去直到遍历完序列的元素 为止算法的复杂度也是简单的，排序第一个需要 1的复杂度，排序第二个需要 2 的复杂度，因此整个的复杂 度就是 1 + 2 + 3 + + N = O 的复杂度。 39 / 49 */ template void InsertSort(T array, int length) T key; for (int indexI = 1; indexI key = arrayindexI; / 把 i之前大于 arrayi的数据向后移动 int indexJ; for (indexJ = indexI - 1; indexJ = 0 & arrayindexJ key; -indexJ) 40 / 49 arrayindexJ + 1 = arrayindexJ; / 在合适位置安放当前元素 arrayindexJ + 1 = key; int main() int array6 = 2, 8, 6, 7, 3, 4; InsertSort(array, 6); for (int index = 0; index != 6; +index) 41 / 49 cout cout 堆排序 #include using namespace std; /* 1 堆排序 2 (1)用大根堆排序的基本思想 3 先将初始文件 R1.n建成一个大根堆，此堆为初始的无序区 42 / 49 4 再将关键字最大的记录 R1(即堆顶 )和无序区的最后一个记录 Rn交换， 5 由此得到新的无序区 R1.n-1和有序区 Rn，且满足 R1.n-1.keysRn.key 6 由于交换后新的根 R1可能违反堆性质，故应将当前无序区 R1.n-1调整为堆。 7 然后再次将 R1.n-1中关键字最大的记录 R1和该区间的最后一个记录 Rn-1交换， 8 由此得到新的无序区 R1.n-2和有序区Rn-1.n ， 且 仍 满 足 关 系 R1.n- 2.keysRn -1.n.keys， 9 同样要将 R1.n-2调整为堆。 10 11 直到无序区只有一个元素为止。 12 (2)大根堆排序算法的基本操作： 13 初始化操作：将 R1.n构造为初始堆； 14 每一趟排序的基本操作：将当前无序区的堆顶记录 R143 / 49 和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆 )。 15 注意： 16 只需做 n-1 趟排序，选出较大的