有人说：STL的sort和手写的快排哪个效率更高呢？听说STL很慢的！考试时该用哪个呢？

下面我们就来验证一下哪种排序算法更高效

STEP1

先来做好准备工作，把几种排序算法的模板写好

STEP2

用 Google 的 benchmark 库测一下这几个排序的算法的渐进复杂度系数

这是插入排序的渐进复杂度是 0.16 N^2，以及系数的标准差是 0.07

这是归并排序的渐进复杂度是 11.58 NlgN，以及系数的标准差是 0.03

这是快速排序的渐进复杂度是 6.98 NlgN，以及系数的标准差是 0.02

这是std :: sort 排序的渐进复杂度是 4.87 NlgN，以及系数的标准差是 0.02

STEP3

摘一下标准库里的sort代码

std :: sort

template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first != __last)
    {
      std::__introsort_loop(__first, __last,
                std::__lg(__last - __first) * 2);
      std::__final_insertion_sort(__first, __last);
    }
    }

STL里快排尾递归主逻辑

/// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator, typename _Size>
    void
    __introsort_loop(_RandomAccessIterator __first,
             _RandomAccessIterator __last,
             _Size __depth_limit)
    {
      while (__last - __first > int(_S_threshold))
    {
      if (__depth_limit == 0)
        {
          _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
          return;
        }
      --__depth_limit;
      _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last);
      std::__introsort_loop(__cut, __last, __depth_limit);
      __last = __cut;
    }
    }

部分排序中使用堆排序

template<typename _RandomAccessIterator>
    inline void
    partial_sort(_RandomAccessIterator __first,
         _RandomAccessIterator __middle,
         _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __middle);
      __glibcxx_requires_valid_range(__middle, __last);

      std::__heap_select(__first, __middle, __last);
      std::sort_heap(__first, __middle);
    }

快排中的partion，这里用的是三分取中

template<typename _RandomAccessIterator>
    inline _RandomAccessIterator
    __unguarded_partition_pivot(_RandomAccessIterator __first,
                _RandomAccessIterator __last)
    {
      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
      std::__move_median_first(__first, __mid, (__last - 1));
      return std::__unguarded_partition(__first + 1, __last, *__first);
    }

  template<typename _RandomAccessIterator, typename _Tp>
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
              _RandomAccessIterator __last, const _Tp& __pivot)
    {
      while (true)
    {
      while (*__first < __pivot)
        ++__first;
      --__last;
      while (__pivot < *__last)
        --__last;
      if (!(__first < __last))
        return __first;
      std::iter_swap(__first, __last);
      ++__first;
    }
    }

最后走优化的插入排序

template<typename _RandomAccessIterator>
    void
    __final_insertion_sort(_RandomAccessIterator __first,
               _RandomAccessIterator __last)
    {
      if (__last - __first > int(_S_threshold))
    {
      std::__insertion_sort(__first, __first + int(_S_threshold));
      std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
    }
      else
    std::__insertion_sort(__first, __last);
    }

结论

可以看出 std::sort 拥有更小的渐进复杂度系数

总结

首先，STL的sort 不仅仅是快排，所以你只是手写快排，哪怕是尾递归式的快排，也不会有它快!

它会先走快排主递归逻辑，但是递归深度是有限的，而且当子区间够小时，会走插入排序，我摘了标准库里几行代码，具体直接看代码就可以了。

另外，你可以看一下我写的几个排序算法和 STL 里的 sort 的对比数据：

STL的sort必然要比你自己写的快排要快，因为你自己手写一个这么复杂的sort，那就太闲了。STL的sort是尽量让复杂度维持在O(N log N)的，因此就有了各种的Hybrid sort algorithm。