排序方法最差时间复杂度最佳时间复杂度平均时间复杂度空间复杂度稳定性
直接插入排序$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,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-10-28
原文链接:https://ethsonliu.com/2019/10/sort-summary.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。