各项指标对比
时空复杂度及稳定性
| 排序算法 | 最好情况 | 最坏情况 | 平均情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(n1.3) | O(n2) | O(1) | 不稳定 | |
| 冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(log2n) | 不稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O® | 稳定 |
对n较大的排序记录。一般的选择都是时间复杂度为 O(nlog2n) 的排序方法。
- 从时间复杂度角度：
- 平方阶排序 O(n2)：直接插入排序、冒泡排序和简单选择排序，这三个一般称为简单排序；
- 线性对数阶排序 O(nlog2n)：快速排序、堆排序和归并排序；
- O(n1+§))排序，§是介于0和1之间的常数：希尔排序；
- 线性阶排序 O(n)：基数排序（计数排序、桶/箱排序）。
原序列有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至 O(n)；
原序列基本有序时，快速排序将蜕化为冒泡排序，时间复杂度提高为 O(n2)；
由于一些数学上的问题为未解决，所以希尔排序的时间复杂度尚无精确渐近时间；
原序列初始状态（是否有序），对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
- 空间复杂度
简单排序、希尔排序和堆排序需要常数个辅助空间用于元素的移动、交换等操作；
快速排序需要一个小递归栈实现递归，平均大小为 O(log2n)，最坏会变成 O(n)；
归并排序需要更多空间用于合并操作；
- 稳定性
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；
稳定排序：直接插入排序、冒泡排序、归并排序、基数排序
不稳定排序：希尔排序、快速排序、选择排序、堆排序
过程特征
| 排序算法 | 一趟排序能否确定一个元素位置 | 能否产生有序子序列 | 局部/全局 |
|---|---|---|---|
| 直接插入排序 | 不能 | 能 | 局部有序 |
| 希尔排序 | 不能 | 不能 | X |
| 冒泡排序 | 能（最值） | 能 | 全局有序 |
| 快速排序 | 能 （基准值） | 不能 | X |
| 简单选择排序 | 能（最值） | 能 | 全局有序 |
| 堆排序 | 能（最值） | 能 | 全局有序 |
| 归并排序 | 不能 | 能 | 局部有序 |
| 基数排序 | 不能 | 不能 | X |
应用场景选择
选用算法的考虑因素
每种排序算法都各有优缺点，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。
影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。
一般而言，需要考虑的因素有以下几点：
1．待排序的元素数目 n 的大小；
2．元素本身数据量的大小，也就是元素中除关键字外的其他信息量的大小；
3．关键字的结构及其分布情况；
4．对排序稳定性的要求；
5. 语言工具条件，存储结构及辅助空间大小等。
选用算法的基本场景
-
当 n 较小（n≤50），可采用直接插入排序或简单选择排序；
直接插入排序移动操作次数较多，如果元素本身信息量较大时，不建议使用，转而用简单选择排序。 -
原序列基本有序时，可选用直接插入排序或冒泡排序；
-
当n较大，则应采用时间复杂度为 O(nlog2n) 的排序方法：快速排序、堆排序、归并排序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序：辅助空间少，不会出现快速排序的最坏情况；
归并排序：相较于前两者，归并排序时稳定的，不过要求的辅助空间较多；归并排序不建议单独使用，通常与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。 -
基数排序是一种稳定的排序算法，但有一定的局限性：
（1）关键字可分解
（2）记录的关键字位数较少，如果密集更好
（3）如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序 -
元素本身信息量很大时，为避免过多的移动操作，可改用（静态）链表存储；但是由于一些排序依赖于存储结构，如希尔排序、快速排序、堆排序等依赖于顺序存储，为了解决这个矛盾，可以进行地址排序，即另设一个地址向量指示相应元素，排序过程中移动地址向量而不移动元素。
基于比较排序的分析
对 n 个记录进行排序至少需进行多少次关键字间的比较？
基于比较的排序，每次比较两个关键字大小后，仅出现两种可能的转移，因此可以用一棵二叉判定树来描述基于“比较”的排序过程，判定树上的每一次比较都是必须的，容易得到，每个初始序列达到最终有序所进行的比较次数，恰好是从树根到该最终序列相应叶子节点的路径长度，即 高度为 h 的判定树，至少要进行 h-1 次比较。
现假设有 n 个元素，可能出现的序列状态有 n! 个，即判定树必须有 n! 个叶子节点，少一个就说明上有两种状态未分辨出来。叶子数为 n! 的完全二叉树的高度（深度）为 ⌈log(n!)⌉+1。
因此基于比较的排序算法，在最坏情况下所需要进行比较的次数至少为 ⌈log(n!)⌉，不过这只是理论下届，一般的排序算法在 n>4 时所需要的比较次数均大于这个值。
1956年，Demuth 首先找到了对 5 个数进行排序只需要 7 次比较的方法后，Lester Ford 和 Selmer Johnson 将其推广，提出了归并插入排序，在 n<11 时所用的比较次数和 ⌈log(n!)⌉ 相同。
根据斯特林公式，⌈log(n!)⌉=O(nlogn)，因此基于比较的排序算法在最坏情况下能达到的最好时间复杂度为 O(nlogn)。