算法 — sort
最后更新于：2022-04-01 19:54:51
能使用STL的sort系列算法的前提是容器的迭代器必须为随机迭代器。所以，vector和deque天然适用。STL的sort算法采用了一些策略，在不同情况下采用不同的排序算法，以达到各种算法优势互补的效果。基本的原则是：数据量大时采用快速排序，数据量小时采用插入排序（这是对快排常用的一种优化策略），递归层次过深改用堆排序。
首先是插入排序。它的平均和最坏时间复杂度都为O(N²)，量级小于千，那么插入排序还是一个不错的选择。SGI STL的插入排序默认以增序排列，另外还可以传入一个仿函数作为比较规则，这里只说明前者。
外层循环确定一个子区间，i位置的元素需要插入到已排序区间的正确位置上：
~~~
template
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
if (first == last) return; // 容器为空，直接返回
for (RandomAccessIterator i = first + 1; i != last; ++i) // 确定子区间
__linear_insert(first, i, value_type(first));
}
~~~
进入__linear_insert函数：
~~~
template
inline void __linear_insert(RandomAccessIterator first,
RandomAccessIterator last, T*) {
T value = *last; // 新插入元素
if (value < *first) { // 如果比已排序区间的第一个元素还要小
copy_backward(first, last, last + 1); // 使已排序区间整体后移一个位置
*first = value; // 新元素放在开头位置
}
else
__unguarded_linear_insert(last, value);
}
~~~
上面代码的注释已经说明了一种简单的情况，这是只需借用copy_backward算法将元素整体搬移，以腾出第一个位置给新插入元素。但其它情况下就要进入__unguarded_linear_insert函数了：
~~~
template
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
RandomAccessIterator next = last; // 指向新插入元素
--next; // 指向之前一个元素
while (value < *next) { // 发现逆转对
*last = *next; // 较大的元素往后走
last = next;
--next;
}
*last = value; // 新元素放入正确位置
}
~~~
上述函数的目标就是要找到value也就是新插入元素的正确插入位置。以value位置为起点，前向遍历已排序区间，遇到比value大的就后移一个位置，以消除逆转对的存在。注意，这里不需要进行越界判断，因为value肯定不会插入到区间头部。
当遇到大数据量时，效率为平方级的插入排序就不适用了。这时STL改用快速排序，平均效率为O(NlogN)，最坏效率为O(N²)。
快排首先要选取枢轴，STL采用的方法是选取前、中、后三点的中值作为枢轴。接下来是分割，遍历整个迭代器，小于枢轴的放左边，大于枢轴的放右边。具体做法如下：
- first迭代器向后移动，*first大于或等于枢轴时停止。
- last迭代器向前移动，*last小于或等于枢轴时停止。
- 若first仍在last的左边，则交换*first和*last，并调整两个迭代器指向下一个位置。
- 重复上述行为直到first和last交叉，first即为右半部分起始位置。
分割代码如下：
~~~
template // 快排的分割函数
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
RandomAccessIterator last,
T pivot) {
while (true) {
while (*first < pivot) ++first; // 向后移动直到*first大于或等于枢轴
--last;
while (pivot < *last) --last; // 向前移动直到*last小于或等于枢轴
if (!(first < last)) return first; // 交叉后停止，返回的迭代器作为右子区间的开头
iter_swap(first, last); // 交换两个迭代器所指元素
++first;
}
}
~~~
现在来看看sort算法的对外接口：
~~~
template
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
if (first != last) {
__introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
__final_insertion_sort(first, last);
}
}
~~~
要阅读__introsort_loop函数，先要了解introsort。以下是维基百科里的解释：
内省排序（英语：Introsort）是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持O(nlogn)的时间复杂度。
个人理解，最坏情况发生在分割深度过深时，以中值作为枢轴的方法并不能选出合适的枢轴，导致分割时频繁地交换元素，使效率下降到O(N)。
上述代码中的__lg(last - first) * 2就是根据元素个数计算深度阈值，当分割深度超过阈值时，转而采用堆排序，是效率继续保持为O(nlogn)。
~~~
template
inline Size __lg(Size n) { // 控制分割恶化的情况，求2^k <= n的最大k值
Size k;
for (k = 0; n != 1; n >>= 1) ++k;
return k;
}
~~~
例如，当元素个数为40时，最多允许分割10层。
有了上面内省排序的基础，下面的代码就很容易看了：
~~~
template
void __introsort_loop(RandomAccessIterator first,
RandomAccessIterator last, T*,
Size depth_limit) {
while (last - first > __stl_threshold) { // 大于某个值才进行快速排序，这里__stl_threshold = 16
if (depth_limit == 0) {
partial_sort(first, last, last); // 分割恶化，采用堆排序
return;
}
--depth_limit;
RandomAccessIterator cut = __unguarded_partition
(first, last, T(__median(*first, *(first + (last - first)/2),
*(last - 1)))); // 采用三点中值作为枢轴进行快速排序
__introsort_loop(cut, last, value_type(first), depth_limit); // 对右半部分递归进行排序
last = cut; // 调整last位置，下一次while循环将对左半部分排序
}
}
~~~
partial_sort已经在另一篇文章中详细分析过了，实际上就是对整个区间进行堆排序。__median函数就是求取前、中、后三个元素中值作为枢轴，其它函数都已经在上面讲解过了。递归分段排序，典型的分治策略。当__introsort_loop函数返回时，要么完全已排序，要么大体已排序。大体已排序则要进行微调，即sort函数调用完__introsort_loop之后调用__final_insertion_sort进行微调：
~~~
template
void __final_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last) {
if (last - first > __stl_threshold) { // 超过16个元素，则分割为两段
__insertion_sort(first, first + __stl_threshold); // 前段使用插入排序
__unguarded_insertion_sort(first + __stl_threshold, last); // 剩余元素逐个插入
}
else
__insertion_sort(first, last); // 元素个数不超过16，直接使用插入排序
}
~~~
注意，为了效率，STL又开始折腾了...，再进入__unguarded_insertion_sort瞧瞧：
~~~
template
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
RandomAccessIterator last, T*) {
for (RandomAccessIterator i = first; i != last; ++i)
__unguarded_linear_insert(i, T(*i)); // 将i所指元素插入已排序的16个元素的序列中，前面已经介绍过了
}
template
inline void __unguarded_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last) {
__unguarded_insertion_sort_aux(first, last, value_type(first));
}
~~~
为什么要这样？当从__introsort_loop函数返回时，要么完全有序，要么大体有序。大体有序时，前面的子区间整体是要小于后面的子区间的，这是introsort操作之后的结果。在__final_insertion_sort中，如果元素个数超过16，先对前16个元素进行插入排序，后面剩下的元素再逐个插入到此有序区间。刚才说了由于已经是大体有序了，所以逐个插入操作不会出现过多的逆转对，这正是插入排序的优势所在。
至此，STL的sort算法分析完了。要读懂STL的心思确实不是意见容易的事情啊。
参考：
《STL源码剖析》 P389.
';