| 排序方法 | 最差时间复杂度 | 最佳时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | O(1) | 稳定 |
| 快速排序 | $O(n^2)$ | $O(nlogn)$ | $O(nlogn)$ | $O(logn)$ | 不稳定 |
| 堆排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | 不稳定 |
| 归并排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 |
（我并未把前面几篇文章所涉及的所有排序算法都列入表格，因为在实际生活中，我们所用的无外乎上面的四种排序，所以我们只需关注这四种算法足矣。当然，排序算法有很多种，有兴趣的读者可以了解下。）
所谓的稳定性，百度百科解释为：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri = rj，且 ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。
这个概念很重要。请考虑这样的场景，有一个表示电子邮件的对象集合，首先按日期进行排序，接着按发件人进行排序，现在你希望它们在每个发件人中都按日期排序，很显然这只有在具备稳定性的排序算法中才会出现这种情况，快速排序和下面即将要讲的 IntroSort 都不符合，即使它们的速度更胜一筹。
当你在 Google 中输入 "heap sort vs quick sort"，"merge sort vs quick sort" 这样的关键词，你会发现一些关于它们之间更深层次的辨析和讨论：
快速排序是一个 In-place algorithm，中文可以译为 "原地算法"，这意味着它有更少的寄存器分配，更好的缓存局部性。
堆排序也是一个 In-place algorithm，但与快速排序相比，堆排序的两两操作数之间的内存跨度更大，并且其交换次数明显大于快速排序，下图是国外一篇文章关于交换次数的测试报告，
作者分别做了 100、1,000、10,000、100,000 和 1000,000 五个数量级的随机序列的测试，共做了 30 次，取其平均值。得出的结果表明，在较低数量级下，它们之间差别很小，但随着数量级越来越大，差距也越来越大。
归并排序并不是一个 In-place algorithm，因为它需要 $O(n)$ 的辅助空间，如果数量级过大，那么这个 $O(n)$ 的辅助空间有的时候会给我们带来很大的麻烦。
我们可以以 STL 中的 sort 为例，它实际上是 IntroSort，全称 Introspective Sort（内省式排序），是 David R.Musser 于 1996 年提出的一种混合式排序算法。
代码如下（摘自Visual Studio 2017，代码并不完整）：
const int _ISORT_MAX = 32; // maximum size for insertion sort
template<class _RanIt, class _Diff, class _Pr> inline
void _Sort_unchecked1(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr& _Pred)
{ // order [_First, _Last), using _Pred
_Diff _Count;
while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)
{ // divide and conquer by quicksort
pair<_RanIt, _RanIt> _Mid =
_Partition_by_median_guess_unchecked(_First, _Last, _Pred);
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
if (_Mid.first - _First < _Last - _Mid.second)
{ // loop on second half
_Sort_unchecked1(_First, _Mid.first, _Ideal, _Pred);
_First = _Mid.second;
}
else
{ // loop on first half
_Sort_unchecked1(_Mid.second, _Last, _Ideal, _Pred);
_Last = _Mid.first;
}
}
if (_ISORT_MAX < _Count)
{ // heap sort if too many divisions
_Make_heap_unchecked(_First, _Last, _Pred);
_Sort_heap_unchecked(_First, _Last, _Pred);
}
else if (2 <= _Count)
_Insertion_sort_unchecked(_First, _Last, _Pred); // small
}宏观来看，STL 之 sort 是 "快排+堆排+直接插入" 三种混合排序的排序算法（很显然它也是不稳定的）。当算法有恶化的倾向时，IntroSort 能够自我检测，转而使用另外的排序算法，保证其时间复杂度。微观来看，利用 _Ideal 来记录快速排序的分割次数，当大于 $1.5log_2n$ 时，转而选择堆排或插入排序，二选其一的基准是此刻待排序元素个数是否大于 $32$，这从代码就可以看出。（当然不同的 STL 版本采用不同的具体实现，比如 SGI STL 也采用了 IntroSort，读者可以参考侯杰所著的《STL 源码剖析》；RW STL 则是纯粹地使用了 QuickSort。）
为什么选择堆排或插入排序，而不是归并排序或插入排序呢？个人觉得，很大一部分原因，就是归并排序的 $O(n)$ 辅助空间。
其它
文章开源在 Github - blog-articles，点击 Watch 即可订阅本博客。 若文章有错误，请在 Issues 中提出，我会及时回复，谢谢。
如果您觉得文章不错，或者在生活和工作中帮助到了您，不妨给个 Star，谢谢。
(文章完)