参考:https://blog.csdn.net/u011386173/article/details/110394829
STL所提供的各式各样的算法中，sort()是最复杂庞大的一个。这个算法接受两个RandomAccessIterators(随机存取迭代器),然后将区间内的所有元素以渐增方式由小到大重新排列。第二个版本则允许用户指定一个仿函数（functor)，作为排序标准。STL的所有关系型容器（associative containers）都有用自动排序功能（底层结构采用RB-tree）,所以不需要用到这个sort算法。至于序列式容器（sequence containers）中的stack、queue和priority-queue都有特别的出入口，不允许用户对元素排序。剩下vector、deque和list，前两者的迭代器属于RandomAccessIterators,适合使用sort算法，list的迭代器则属于BidirectioinalIterators，不在STL标准之列的slist，其迭代器更属于ForwardIterator，都不适合使用sort算法。如果要对list或slist排序，应该使用它们自己提供的member functions sort()。
STL的sort算法， 数据量大时采用Quick Sort，分段递归排序。一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来过大的额外负荷（overhead）,就改用 Insertion Sort。如果递归层次过深，还回改用 Heap Sort。 —— From《STL源码剖析》
源码：
stl_algo.h：
template <class _RandomAccessIter>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
_LessThanComparable);
if (__first != __last) {
__introsort_loop(__first, __last,
__VALUE_TYPE(__first),
__lg(__last - __first) * 2); //快速排序
__final_insertion_sort(__first, __last); //插入排序
}
}
template <class _RandomAccessIter, class _Tp, class _Size>
void __introsort_loop(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*,
_Size __depth_limit)
{
while (__last - __first > __stl_threshold) {
//1、__depth_limit 是控制递归深度
if (__depth_limit == 0) {
partial_sort(__first, __last, __last); //递归深度过深时采用堆排序
return;
}
--__depth_limit;
//2、单边递归
_RandomAccessIter __cut =
__unguarded_partition(__first, __last,
_Tp(__median(*__first,
*(__first + (__last - __first)/2),
*(__last - 1)))); //3、__median三点取中法
__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);
__last = __cut;
}
}
template <class _RandomAccessIter>
inline void partial_sort(_RandomAccessIter __first,
_RandomAccessIter __middle,
_RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
_LessThanComparable);
__partial_sort(__first, __middle, __last, __VALUE_TYPE(__first));
}
template <class _RandomAccessIter, class _Tp>
void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
_RandomAccessIter __last, _Tp*) {
make_heap(__first, __middle); //线性建堆
for (_RandomAccessIter __i = __middle; __i < __last; ++__i) //堆排序
if (*__i < *__first)
__pop_heap(__first, __middle, __i, _Tp(*__i),
__DISTANCE_TYPE(__first));
sort_heap(__first, __middle); //堆排序
}
template <class _RandomAccessIterator>
inline void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
_LessThanComparable);
__make_heap(__first, __last,
__VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
}
template <class _RandomAccessIterator, class _Tp, class _Distance>
void
__make_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Tp*, _Distance*)
{
if (__last - __first < 2) return;
_Distance __len = __last - __first;
_Distance __parent = (__len - 2)/2;
while (true) { //线性建堆
__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
if (__parent == 0) return;
__parent--; //__parent就是线性建堆时逆序扫描
}
}
总结来说，STL 中的排序算法sort有3个步骤：
控制递归深度 --> 使用了堆排序 --> 线性建堆
单边递归
三点取中
排序区间大小：当排序区间大的时候使用了快速排序，当排序区间过小的时候停止快速排序，使用插入排序。也就是说经过快速排序后，整段空间被分割为了几段，每段里面的数不是有序的，但是第一段的所有数都小于第二段，第二段的所有数都小于第三段…，最后对每一段插入排序使其成为有序序列。
也就是说sort算法将三种排序进行了融合：
对于区间较大的情况，使用了快速排序；
当递归深度过深时，使用堆排序；
最终的排序整理，使用插入排序。
即STL中的sort算法是快排、插入排序和堆排序的综合
