排序（6）：总结

• 2017 年 07 月 02 日
• • 技术

系列文章目录

排序（1）：直接插入排序，二分查找插入排序，希尔排序
排序（2）：快速排序
排序（3）：堆排序
排序（4）：归并排序
排序（5）：基数排序
排序（6）：总结

排序方法

最差时间复杂度

最佳时间复杂度

平均时间复杂度

空间复杂度

稳定性

直接插入排序

$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)$

稳定

基数排序

$×$

$×$

$O(k⋅n)$

$O(n)$

稳定

所谓的稳定性，百度百科解释为：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri = rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

我并未把前面几篇文章所涉及的所有排序算法都列入表格，因为在实际生活中，我们所用的无外乎上面的5种排序，所以我们只需关注这5种算法足矣。

当然，排序算法有很多种，有兴趣的读者可以了解下。

最后不得不说下STL之sort的实现技巧。STL之sort并非QuickSort，而是IntroSort。

IntroSort，是David R.Musser于1996年提出的一种混合式排序算法：Introspective Sort（内省式排序），简称IntroSort。

代码如下（摘自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。