排序算法性能及选择总结¶

各种排序方法的性能比较：

排序法	平均时间	最坏情况	最好情况	稳定度	额外空间	备注
1．直接插入	O(n2)	O(n2)	O(n)	稳定	O(1)	大部分已排序时较好（简单）
1．希尔	O(nlogn)	O(nlogn)	与步长相关	不稳定	O(1)	n 小时较好（较复杂）
2．冒泡	O(n2)	O(n2)	O(n)	稳定	O(1)	n 小时较好（简单）
2．快排	O(nlogn)	O(n2)	O(nlogn)	不稳定	O(logn)	n 大时较好, 基本有序时反而不好（较复杂）
3．直接选择	O(n2)	O(n2)	O(n2)	不稳定	O(1)	n 小时较好（简单）
3．堆排序	O(nlogn)	O(nlogn)	O(nlogn)	不稳定	O(1)	n 大时较好（较复杂）
4．归并	O(nlogn)	O(nlogn)	O(nlogn)	稳定	O(n)	n 大时较好（较复杂）
基数	O(d(n+r))	O(d(n+r))	O(d(n+r))	稳定	O(r)	d 为位数，r 为基数（较复杂）
计数	O(n+k)	O(n+k)	O(n+k)	稳定	O(n+k)	优于比较排序法,0~k 为数值范围
桶排序	O(n+c)	O (nlogn): 所有的元素落到一个桶中	O(n)	稳定	O(n+m)	n 为数的个数，m 为桶数 c = n*(logn-logm) 桶越多，效率越高，n=m, 达到 O(n)，但是占用很大的空间，桶内可用快排等

（一）基于比较的排序算法：

1. 第一类——插入排序法：直接插入排序，希尔。以及不常见的 Tree sort、Library sort、Patience sorting 。

2. 第二类——交换排序法：冒泡、快排（由冒泡改进而来）。以及不常见的鸡尾酒排序、奇偶排序、梳排序、Gnome sort 。

3. 第三类——选择排序法：直接选择、堆排序。

4. 第四类——归并排序法：归并排序。以及不常见的 Strand sort。

（二）非基于比较的排序算法：

上表中蓝色粗体标识：基数、计数、桶排序。

==================================================

性能分析及选择排序方法的考量：

O(n^2) 的分析：在数据规模较小时 (9W 之内)，直接插入（略微好于简单选择）、简单选择差不多。当数据较大时，冒泡排序算法的时间代价是最昂贵的。 另外，普通排序算法基本上都是相邻元素进行比较，因此 O(N^2) 的排序基本都是稳定的。

O(nlogn) 的分析：其中快速排序无疑是最优秀的。其次是归并排序和希尔排序，堆排序稍微差一些。

先进算法分析：

(1) 就时间性能而言，希尔排序、快速排序堆排序和归并排序都是较为先进的排序方法。耗时远小于 O(N^2) 级别的算法。

(2) 先进算法之中，快排的效率是最高的。但其缺点十分明显：在待排序列基本有序的情况下，会蜕化成起泡排序，时间复杂度接近 O(N^2)。

(3) 希尔排序的性能让人有点意外，这种增量插入排序的高效性完全说明了：在基本有序序列中，直接插入排序绝对能达到令人吃惊的效率。但是希尔排序对增量的选择标准依然没有较为满意的答案，要知道增量的选取直接影响排序的效率。

(4) 归并排序的效率非常不错，在数据规模较大的情况下，它比希尔排序和堆排序都要好。

(5) 堆排序在数据规模较小的情况下还是表现不错的，但是随着规模的增大，时间代价也开始和 shell 和归并两种排序拉开距离。

(6) 多数先进排序都因为跳跃式的比较，降低了比较次数，但是也牺牲了排序的稳定性。

总的来说，并不存在 “最佳” 的排序算法。必须针对待排序列自身的特点来选择 “良好” 的算法。下面有一些指导性的意见：

(1) 数据规模很小，而且待排序列基本有序的情况下，选择直接插入排序绝对是上策。不要小看它 O(N^2) 级别。

(2) 数据规模不是很大，完全可以使用内存空间。而且待排序列杂乱无序 (越乱越开心)，快排永远是不错的选择，当然付出 log(N) 的额外空间（为栈所需的辅助空间）是值得的。

(3) 海量级别的数据，必须按块存放在外存 (磁盘) 中。此时的归并排序是一个比较优秀的算法。

1. 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。

反而在这种情况下，快速排序反而慢了。

1. 当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。

2. 若待排序的记录的关键字在一个明显有限范围内时, 且空间允许是用桶排序。

3. 当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

4. 当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下, 宜用归并排序。

5. 当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

=====================================================================

各种排序方法比较

简单排序中直接插入最好; 快速排序最快; 当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素： 　　 ① 待排序的记录数目 n； 　　 ② 记录的大小 (规模)； 　　 ③ 关键字的结构及其初始状态； 　　 ④ 对稳定性的要求； 　　 ⑤ 语言工具的条件； 　　 ⑥ 存储结构； 　　 ⑦ 时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1) 若 n 较小 (如 n≤50)，可采用直接插入或直接选择排序。 　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。 (2) 若文件初始状态基本有序 (指正序)，则应选用直接插人、冒泡或随机的快速排序为宜； (3) 若 n 较大，则应采用时间复杂度为 O(nlgn) 的排序方法：快速排序、堆排序或归并排序。 　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 　若要求排序稳定，则可选用归并排序。但从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

(4) 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。 　当文件的 n 个关键字随机分布时，任何借助于 " 比较 " 的排序算法，至少需要 O(nlgn) 的时间。 　箱排序和基数排序只需一步就会引起 m 种可能的转移，即把一个记录装入 m 个箱子之一，因此在一般情况下，箱排序和基数排序可能在 O(n) 时间内完成对 n 个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合 (例如实数型关键字) 时，无法使用箱排序和基数排序，这时只有借助于 " 比较 " 的方法来排序。 　若 n 很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为数字时，则其值均是非负的，否则将其映射到箱 (桶) 号时，又要增加相应的时间。 (5) 有的语言 (如 Fortran，Cobol 或 Basic 等) 没有提供指针及递归，导致实现归并、快速 (它们用递归实现较简单) 和基数 (使用了指针) 等排序算法变得复杂。此时可考虑用其它排序。 (6) 上面的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量 t 作为辅助表，排序前令 t[i]=i(0≤i<n)，若排序算法中要求交换 R[i] 和 R[j]，则只需交换 t[i] 和 t[j] 即可；排序结束后，向量 t 就指示了记录之间的顺序关系： R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key 若要求最终结果是： R[0].key≤R[1].key≤…≤R[n-1].key 则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是 O(n)。

====================================================

1 快速排序（QuickSort）

快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。

（1） 如果不多于 1 个数据，直接返回。 （2） 一般选择序列最左边的值作为支点数据。 （3） 将序列分成 2 部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4） 对两边利用递归排序数列。快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。

2 归并排序（MergeSort）

归并排序先分解要排序的序列，从

1 分成 2，2 分成 4，依次分解，当分解到只有 1 个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。

3 堆排序（HeapSort）

堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

4 Shell 排序（ShellSort）

Shell 排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是 O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用 D.E.Knuth 的分组方法。

Shell 排序比冒泡排序快 5 倍，比插入排序大致快 2 倍。Shell 排序比起 QuickSort，MergeSort，HeapSort 慢很多。但是它相对比较简单，它适合于数据量在 5000 以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

5 插入排序（InsertSort）

插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快

2 倍。一般不用在数据大于 1000 的场合下使用插入排序，或者重复排序超过 200 数据项的序列。

6 冒泡排序（BubbleSort）

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是

O(n^2) 的算法。

7 交换排序（ExchangeSort）和选择排序（SelectSort）

这两种排序方法都是交换方法的排序算法，效率都是

O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。

8 基数排序（RadixSort）

基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。

=============================================

常考问题：

1. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

2. 直接插入排序在某一趟结束后未必能选出一个元素放在其最终位置；但是堆排序、冒泡（在首趟即可确定最大值和最小值）、快排可以。

3. 已知数组中的每个元素距离最终位置不远，采用直接插入排序最节省时间。

4. 直接选择排序关键字比较次数和记录的初始排列顺序无关，都为 n(n-1)/2。

5. 对 n 个元素执行快排，在进行第一次划分时，关键字的比较次数总是 n-1。