前端面试题：如何排序一个长度为10000的数组？

Question

这个题目要选取哪一个排序算法比较好呢？

谢谢！

Answer 1

据说，大于1000用快排，小于1000用冒泡就行

Answer 2

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

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

代码如下（摘自 Visual Studio 2015，代码并不完整）：

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 能够自我检测，转而使用另外的排序算法，保证其时间复杂度，此即所谓的“扬长避短”。

摘自:http://www.61mon.com/index.ph...

Answer 3

10000的情况一般的n^2排序都能在1s之内跑完，不一定要用nlogn的，插入排序可能常数比较小，但是我觉得最好写的是选择排序。