STL里sort算法简析

@[toc]

一、引入

如果面试官给你出了一道面试题：STL里sort算法用的是什么排序算法？

•  当你第一眼看到这道面试题是不是心里在暗喜，因为排序讲的是效率，时间复杂度越小越好，并且作为STL的标准算法，更因该注重效率，这时你的脑海里想的肯定是快排
•  此时如果你回答：
•  STL里的sort算法肯定用的是快速排序啊？难不成还是冒泡排序么？那么恭喜你，你可能错失了大厂的机会，如果面试官不提醒你，你可能觉得自己面的还可以
•  嘿嘿😁～～～

如果你回答的是快排并且面试官没有放弃你的话，你可能会遇到如下问题：

•  数据量大和数据量小都适合用快速排序吗？
•  快速排序的时间复杂度不是稳定的nlogn，最坏情况会变成n^2，怎么解决复杂度恶化问题？
•  快速排序递归实现时，怎么解决递归层次过深的问题？
•  递归过深会引发什么问题？
•  怎么控制递归深度？如果达到递归深度了还没排完序怎么办？

如果面试官问你了，那么说明你的大厂offer正在向你靠近，因为这些问题并不是你不会，只不过是没没把重心放在那方面而已

二、正解

•  1.sort函数提供了两个版本
•  sort(first, last)：默认按照小于方式排序，排序结果为升序，一般用排内置类型数据
•  sort(first, last, comp)：可以通过comp更改元素比较方式，即可以指定排序的结果为升序或者降序，一般以仿函数对象和函数指针的方式提供
•  2.sort并不是一种排序算法，而是将多个排序算法混合而成
•  3. 当元素个数少于__stl_threshold阈值时(16)，使用直接插入排序处理
•  4. 当元素个数超过__stl_threshold时，考虑是否能用快排的方式排序，因为当元素数量达到一定程度，递归式的快排可能会导致栈溢出而崩，因此：
•  通过__lg函数判断递归的深度
•  5.如果递归的深度没有超过2*lg（n） 时，则使用快排方式排序，注意：快排时使用到了三数取中法预防分割后一边没有数据的极端情况
•  如果递归深度超过2*lg（n） 时，说明数据量大，递归层次太深，可能会导致栈溢出，此时使用堆排序处理

是不是很惊喜，很意外？

为什么？直接看STL源码实现，来源于侯捷老师翻译的鼎鼎大名的 《STL源码剖析》 关于sort算法实现的细节，实现细节有很多精彩的地方。

总结：sort算法用到了快速排序，但不仅仅只用了快速排序，还结合了插入排序和堆排序。

三、源码

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);
        }
    }

其中，__introsort_loop便是内省式排序:

template <class _RandomAccessIter, class _Tp, class _Size>

void __introsort_loop(_RandomAccessIter __first,
				_RandomAccessIter __last, _Tp*,_Size __depth_limit)
{
 
	while (__last - __first > __stl_threshold) {
 
		if (__depth_limit == 0) {
 
			partial_sort(__first, __last, __last);
 
			return;
 
		}
 
		--__depth_limit;
 
		_RandomAccessIter __cut =
 
		__unguarded_partition(__first, __last, _Tp(__median(*__first,
			*(__first + (__last - __first) / 2),*(__last - 1))));
 
		__introsort_loop(__cut, __last, (_Tp*)0, __depth_limit);
 
		__last = __cut;
 
	}
	 
}

•  这里进来之后会 首先进行判断元素是否大于__stl_threshold， __stl_threshold是一个常量值是16，意思就是说我传入的元素规模小于我们的16的时候我们就没必要采用我们的内省式算法，直接退回去采用我们的插入排序。
  
•  这里能看到我们的内省式算法结束之后就是我们的插入排序函数。

插入排序

template<typename _RandomAccessIterator>
    void
    __final_insertion_sort(_RandomAccessIterator __first,
                           _RandomAccessIterator __last)
    {
      if (__last - __first > int(_S_threshold))
        {
        //先排前16个
          std::__insertion_sort(__first, __first + int(_S_threshold));
        //后面元素遍历插入到前面有序的正确位置 
         std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
        }
      else
        std::__insertion_sort(__first, __last);
    }

•  如果说我们的 元素规模大于我们的16了，那就需要去判断如果我们是不是能采用快速排序，怎么判断呢？快排是使用递归来实现的，如果说我们进行判断我们的递归深度没有到达我们的最深层次上边的函数已经看过了，最深是2*lg（n）。那我们就去使用我们的快速排序来进行排序

快速排序实现代码

template <class _RandomAccessIter, class _Tp>

_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
_RandomAccessIter __last,_Tp __pivot)
{
 
	while (true) {
 
		while (*__first < __pivot)
 
			++__first;
 
			--__last;
 
			while (__pivot < *__last)
 
				--__last;
 
			if (!(__first < __last))
 
				return __first;
 
			iter_swap(__first, __last);
 
			++__first;
		}
}

•  如果说大于我们的最深层次的话，这里就会采用我们的堆排序，进行排序。
•  当进行完这个过程的时候要明白，这里并不是说整个传进来的数组都是这个过程，这里我们是进行的一次排序，他可能是我传入的数组，也可能是我在进行快排分割之后的左半部分，排序结束之后再去排我的右半部分，所以可以看上边我们的元素规模是不是大于__stl_threshold这个阈值的时候是一个while循环。

函数__lg()防止栈溢出

其第三个参数中所调用的函数__lg()便是用来控制分割恶化情况。代码如下：

template <class Size>
 
inline Size __lg(Size n) {
 
	Size k;
 
	for (k = 0; n > 1; n >>= 1) ++k;
 
	return k;
 
}