MENU

Catalog

    排序(6):总结

    June 9, 2018 • 技术

    系列文章目录

    排序(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。

    Archives QR Code Tip
    QR Code for this page
    Tipping QR Code