C++STL中sort排序算法的底层实现方式和常见问题
STL其他内容解析：关于C++中STL的理解和应用
常见问题：
- 数据量大和数据量小都适合用快速排序吗？
- 快速排序的时间复杂度不是稳定的nlogn，最坏情况会变成n^2，怎么解决复杂度恶化问题？
- 快速排序递归实现时，怎么解决递归层次过深的问题？
- 递归过深会引发什么问题？
- 怎么控制递归深度？如果达到递归深度了还没排完序怎么办？
并非所有容器都使用sort算法
既然问的是STL的sort算法实现，那么先确认一个问题，哪些STL容器需要用到sort算法？
首先，关系型容器拥有自动排序功能，因为底层采用RB-Tree，所以不需要用到sort算法。
其次，序列式容器中的stack、queue和priority-queue都有特定的出入口，不允许用户对元素排序。
剩下的vector、deque，适用sort算法。
实现逻辑
STL的sort算法，数据量大时采用快速排序算法，分段归并排序。一旦分段后的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用插入排序。如果递归层次过深，还会改用堆排序。
所以，STL的sort是结合快速排序-插入排序-堆排序三种排序算法的一种排序实现。
思考：
1.为什么对于区间小于16的采用快速排序，如果递归深度恶化改用堆排序？
插入排序对于基本有序或数据较少的序列很高效。
堆排序的时间复杂度固定为O(nlogn)，不需要再递归下去了。
2.那堆排序既然也是O(nlogn）直接用堆排序实现sort不行吗？为啥用快速排序实现？
第一点，堆排序数据访问的方式没有快速排序友好。对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。 比如，堆排序中，最重要的一个操作就是数据的堆化。比如下面这个例子，对堆顶节点进行堆化，会依次访问数组下标是 1，2，4，8 的元素，而不是像快速排序那样，局部顺序访问，所以，这样对 CPU 缓存是不友好的。
第二点，对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。我们在讲排序的时候，提过两个概念，有序度和逆序度。对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。快速排序数据交换的次数不会比逆序度多。