stl的sort和手写快排的运行效率哪个比较高？

====== 11.11 日更新

今天上午来用Google的 benchmark 库测了一下这几个排序的算法的渐进复杂度系数，环境是在 VBox debian 虚拟机里，分了两个核。

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

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

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

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

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

================== 原答案

首先，STL的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);
    }

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

用例中绿色区域的快速排序：

void swap(int *array, int pos_i, int pos_j) {
    int tmp = array[pos_i];
    array[pos_i] = array[pos_j];
    array[pos_j] = tmp;
}
int partition(int *array, int begin, int end);
// 尾递归版 这个可以减少栈空间的使用
void quick_sort_tail(int *array, int begin, int end) {
    while (begin < end) {
        int r = partition(array, begin, end);
        quick_sort_tail(array, begin, r - 1);
        begin = r + 1;
    }
}

int partition(int *array, int begin, int end) {
    // 在 begin 到 end 间随机找一个数 当 划分用的 key
    int rand_location = rand() % (end - begin + 1) + begin;
    int key = array[rand_location];
    // 把这个 key 移到 end 的位置，方便做双下标前移动
    swap(array, rand_location, end);
    int i = begin - 1;
    for (int j = begin; j < end; ++j) {
        if (array[j] <= key) {
            i++;
            swap(array, i, j);
        }
    }
    swap(array, i + 1, end);
    return i + 1;
}