本文是个人对 C++ 标准库里的 std::sort 函数的分析、解读。鉴于个人能力有限，文中若有错误、疏漏还请各位来打我啊多多调指教QAQ
当然，各家编译器的实现可能不同，这里我是用的是 LLVM 的实现。
LLVM > libcxx release 37 > algorithm
即 Xcode 8.2.1 中所使用的版本。其实在某一行上的实现方式有微小的不同，但是实际上是等价的。而且那一行也不涉及到这里讨论的 std::sort 函数。
这篇 post 由以下几个部分构成
- 引入
- 真正的 sort 实现
- 0 ~ 5 个元素时的排序
- __sort3 的实现
- __sort4, __sort5 的实现
- 6 ~ limit 的实现
- 较大规模时的实现
- 不完全的插入排序
- 总结
- 附带注释的 std::sort
引入
假设有一组由 vector 保存的元素。这里为了简单，我们使用 int 这种基本数据类型，并且直接指定为一组数字。
std::vector<int> array{2, 8, 5, 7, 3, 9, 1, 0, 5};
当我们准备调用 std::sort 时，可以看到，IDE 的代码提示告诉我们有 5 种不同的 std::sort。
阅读 algorithm 的源代码，可以发现其实后四种最终都是调用的
template <class _RandomAccessIterator, class _Compare> inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)>
于是从这个函数开始分析吧。在 algorithm 中的实现如下
// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare template <class _RandomAccessIterator, class _Compare> inline_LIBCPP_INLINE_VISIBILITY void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { #ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __sort<_Comp_ref>(__first, __last, __c); #else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sort<_Comp_ref>(__first, __last, __comp); #endif // _LIBCPP_DEBUG }
首先需要一个可以随机访问的迭代器，如果是使用了 STL 容器的话。如果是普通的数组的话，就直接传递地址。然后是一个比较函数的类型，既可以使用 std::less 或者 std::greater，也可以根据自己的需求传入一个 lambda 函数，传入 lambda 函数时，_Compare 类型会由编译器自动推导。
std::sort 函数传入需要排序的第一个元素和最后一个元素的位置。然后是刚才说的比较大小的函数，这个函数将会被传入两个元素，并且返回这两个元素的比较大小之后的结果。需要注意的是，这个比较必须是严格小于（仅当 “a 小于 b” 时才返回 true），而不能是返回一个 “a 小于等于 b” 的比较结果。
在函数体中，有一个用于 libcxx 调试时的宏，这里我们直接看 release 部分的代码。
typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sort<_Comp_ref>(__first, __last, __comp);
先是给模版的 _Compare 类型定义了一个的左值引用类型，这里是为了之后我们递归调用自己时，能够保持比较函数使用引用方式进行传递。然后第二行调用了真正的排序实现。
真正的 sort 实现
/// 具体实现的函数 /// _RandomAccessIterator 支持随机访问的迭代器 /// _Compare 比较函数的类型 /// __first 需要排序的开始的地方 /// __last 需要排序的结束的地方 /// __comp 比较函数 template <class _Compare, class _RandomAccessIterator> void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
可以看到，这个模版函数将 _Compare 类型放到了 _RandomAccessIterator 类型之前，这是为了之后递归调用时只需要写明 _Compare 的类型，而 _RandomAccessIterator 类型由编译器推导。
在有了第一个元素和最后一个元素的位置（我们将迭代器当作指针使用）之后，需要得到一共有多少个元素，元素的个数决定了排序的规模和我们的策略。但是对于真正的迭代器类型，两个迭代器相减，可能有不同的返回值类型，为了避免type casting，我们使用 type_traits 中提供的 std::iterator_traits 获得差值类型。
typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
有了迭代器做减法所得到的差值的类型之后，我们还需要迭代器本身指向的元素的类型。
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
为什么需要这个 value_type 呢，因为在 C++ 中，一个（广义的）对象可能是用户自己定义的 class、struct 或者 union，又或者是诸如 int、double 这样的基本数据类型。单个基本数据类型在构造 (construct) 或赋值 (assign) 时产生的开销我们可以忽略不计，但如果是用户定义的类型，则会根据具体情况而变化。例如用户自己显式定义了对象的复制构造函数，在这个函数中做了大量数据的复制操作。（在显示定义了对象的复制复制函数也有类似的情况）
于是这一点决定了我们的策略，即在什么规模下，我们使用某种排序方式（稍后则会提到）是可接受的。于是有了这一句判断
const difference_type __limit = std::is_trivially_copy_constructible<value_type>::value && std::is_trivially_copy_assignable<value_type>::value ? 30 : 6;
刚才简单的解释了为什么要这两个条件，接下来解释这两个条件的含义以及成立的要求。
对第一个，std::is_trivially_copy_constructible。先抛开 trivially 这个修饰词，copy constructible type（可复制构造类型）的含义很简单，如果一个类型有显式或隐式的复制构造函数，那么就是可复制构造的
A copy constructible class is a class that has a copy constructor (either its implicit constructor or a custom defined one).
那么加上前面的 trivially 这个修饰词之后呢？trivially copy constructible type（简单复制构造类型) 是指一个可以通过同类型的值或者引用构造的类型。标量类型、可以简单复制构造的类 和 数组 都是这种类型。
A trivially copy constructible type is a type which can be trivially constructed from a value or reference of the same type. This includes scalar types, trivially copy constructible classes and arrays of such types.
简单复制构造的类是这样一种类（它通过class, struct, union关键字定义）：
- 使用隐式定义的复制构造函数
- 没有virtual成员
- 它的基类和非静态数据成员（如果有的话），也必须是简单复制构造类型
下一个条件，is_trivially_copy_assignable。与上面的类似，如果说一个类型是copy assignable的话，那么它有显式或隐式的复制赋值函数。加上前面的 trivially 这个修饰词之后，即如果说一个类型是 trivially copy assignable的话，那么
- 使用隐式定义的复制赋值函数
- 没有virtual成员
- 它的基类和非静态数据成员（如果有的话），也必须是简单复制赋值类型
0 ~ 5 个元素时的排序
之后是一个超大的 while 循环，我们先来看它的前面部分（加上注释之后）
while (true) { __restart: // 拿到需要排序的元素的长度 difference_type __len = __last - __first; // 处理长度为 0 到 5 时的排序 switch (__len) { // 长度为 0 或 1 时就无需排序了 case 0: case 1: return; case 2: // 只有2个元素时，直接比较并交换（如果需要交换的话） if (__comp(*--__last, *__first)) swap(*__first, *__last); return; case 3: // 只有3个元素时，同样直接比较并交换（不过加了一层函数调用，稍后分析） _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return; case 4: // 只有4个元素时，同上 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return; case 5: // 只有5个元素时，同上 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return; }
__sort3 的实现
那么 0 到 2 个元素时就不说了，看看 __sort3 做了什么。
// stable, 2-3 compares, 0-2 swaps template <class _Compare, class _ForwardIterator> unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
可以看到，这是只有 3 个元素时的排序函数，它使用 2 到 3 次比较，0 到 2 次交换即可完成，排序完成时，有 \(x <= y <= z\)（他们所指向的元素的大小），返回值为 swap 的次数。三个数比较大小并排序的逻辑比较简单，直接看代码就能明白，但请再次注意，x、y、z是指针，我们交换的是指向的元素的值，指针本身指向的位置并没有改变。知道这一点的话，注释读起来就很简单了。
template <class _Compare, class _ForwardIterator> unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) { unsigned __r = 0; if (!__c(*__y, *__x)) // if x <= y { if (!__c(*__z, *__y)) // if y <= z return __r; // x <= y && y <= z // x <= y && y > z swap(*__y, *__z); // x <= z && y < z __r = 1; if (__c(*__y, *__x)) // if x > y { swap(*__x, *__y); // x < y && y <= z __r = 2; } return __r; // x <= y && y < z } if (__c(*__z, *__y)) // x > y, if y > z { swap(*__x, *__z); // x < y && y < z __r = 1; return __r; } swap(*__x, *__y); // x > y && y <= z __r = 1; // x < y && x <= z if (__c(*__z, *__y)) // if y > z { swap(*__y, *__z); // x <= y && y < z __r = 2; } return __r; } // x <= y && y <= z
__sort4, __sort5 的实现
在看懂 __sort3 之后，__sort4 和 __sort5 其实就很简单了。先来看 __sort4
// stable, 3-6 compares, 0-5 swaps template <class _Compare, class _ForwardIterator> unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c)
它接受 5 个参数，第一个到第四个是需要排序的 x1, x2, x3, x4，最后一个仍是比较函数。__sort4 的想法非常简单，不论你传入的顺序是什么，__sort4 都利用 __sort3 将 x1, x2, x3 排好序，最后找准 x4 的位置就行，找位置的方式是将 x4 与排序好的三个数按从大到小的顺序比较，即先和 x3 比较，若 x4 大于等于 x3，则顺序是 x1, x2, x3, x4。若 x4 小于 x3，则交换 x4 和 x3 指向的元素的值（指针本身指向的位置并没有改变），然后将 x3（x3 指向的元素就是原来 x4 所指向的） 和 x2 比较……以此类推。
// stable, 3-6 compares, 0-5 swaps template <class _Compare, class _ForwardIterator> unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) { // 先利用__sort3 将 x1, x2, x3 排好序 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); // 此时有 x1 <= x2 <= x3 // 接下来找好 x4 的位置 if (__c(*__x4, *__x3)) { // 如果 x4 < x3 // 交换 x3 和 x4 swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { // 如果 x3 < x2 // 交换 x2 和 x3 swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { // 如果 x2 < x1 // 交换 x1 和 x2 swap(*__x1, *__x2); ++__r; } } } return __r; }
接下来的 __sort5 和 __sort4 的做法几乎一样，除了先是使用 __sort4 排序好前四个之外。
// stable, 4-10 compares, 0-9 swaps template <class _Compare, class _ForwardIterator> unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { // 先将 x1, x2, x3, x4 排好序 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); // 此时有 x1 <= x2 <= x3 <= x4 // 接下来找好 x5 的位置 if (__c(*__x5, *__x4)) { // 如果 x5 < x4 // 交换 x4 和 x5 swap(*__x4, *__x5); ++__r; if (__c(*__x4, *__x3)) { // 如果 x4 < x3 // 交换 x3 和 x4 swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { // 如果 x3 < x2 // 交换 x2 和 x3 swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { // 如果 x2 < x1 // 交换 x1 和 x2 swap(*__x1, *__x2); ++__r; } } } } return __r; }
以上是需要排序的元素在 0 到 5 个时的处理。
6 ~ limit 的实现
接下来，还记得我们一开始声明的那个 __limit 变量吗，当我们排序的对象是 trivially copy constructible 且 trivially copy assignable 的时候，__limit 的值为30，否则则为6。那么它限制的是什么呢？就是排序规模在\((5, \_\_limit]\)时的策略。当排序的元素个数处于\((5, \_\_limit]\)时，
if (__len <= __limit) { _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); return; }
这里调用了 __insertion_sort_3 来排序。这个比较简单，是一个插入排序，并且要求至少有 3 个元素。这里的插入排序与教科书一样的插入排序略有一些区别。
template <class _Compare, class _RandomAccessIterator> void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
这里的插入排序接受的参数和 __sort 相同，然后因为需要一个临时变量，所以也先定义了一下 value_type
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
随后利用刚才的 __sort3 将前三个元素排好序。于是排好序的长度为 3，并且使用 __j 指向排好序的末尾。
接下来令 __i = __j + 1，即 __i 指向排好序的部分的后一个元素，然后将 __i 指向的元素和 __j 指向的元素比较，如果 __i 指向的元素大于等于 __j 指向的元素，那么说明已经排好的部分，再加上 __i 指向的元素 所组成的部分也是排好序的。此时让 __j 指向新的末尾，即将 __i 赋值给 __j，这里的赋值是改变 __j 指向的位置，而不是改变 __j 所指向的元素的值。
那如果刚才 __i 指向的元素小于 __j 指向的元素呢？那么我们需要为 __i 指向的元素找到它应该在的位置（在排好序的部分中插入 __i 所指向的这个元素），查找的方式是先将 __i 指向的元素保存到一个临时变量中，然后从排好序的末尾开始，让那个元素往后移一位，再将临时变量与前一个比较，若结果还是小于，则将前一个也往后移一位……直到临时变量大于等于某个数，或者到了头的时候才停止。
例如 4 个数时，前三个已经排好序。
$$1\quad 3\quad 4\quad 2$$
此时先将 2 和 4 比较，得出 2 小于 4，于是将 2 保存到临时变量中，将 4 往后移一位，有
$$1\quad 3\quad 4\quad 4$$
再将 2 和 3 比较，得出 2 小于 3，于是再将 3 往后移一位，有
$$1\quad 3\quad 3\quad 4$$
最后，将 2 和 1 比较，得出 2 大于 1，于是将 2 写入 1 之后的那个位置，有
$$1\quad 2\quad 3\quad 4$$
此时排序完成。
template <class _Compare, class _RandomAccessIterator> void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 定义迭代器里面所用的值类型 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; // 先将传入的前三个排好序 _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); // 为已经排好序的部分的后一个元素 i 找位置 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { // 将 __i 所指向的元素与已经排好的最后那个比较 if (__comp(*__i, *__j)) { // 若 __i 所指向的元素小于排好序的最后那个元素 // 则说明需要把这第 i 个插入到已经排好序的里面 // 将 __i 所指向的元素保存到临时变量 t 里 value_type __t(_VSTD::move(*__i)); // 然后将把排好序部分，从尾到头，一个一个向后移动 // 直到 t 正好大于某个数 或者 到了头的时候 停止 // 使用 __k 来每次做比较 _RandomAccessIterator __k = __j; // 使用 __j 来作为每次赋值的位置 __j = __i; do { // 将 __k 指向的元素的值赋值到 __j 指向的位置上 *__j = _VSTD::move(*__k); // 更新 __j 指向的位置 __j = __k; } while (__j != __first && __comp(__t, *--__k)); // 若 __j 还不是第一个位置 // (__k 移动到 __k 的前一个位置之后)，t 的值比 __k 的值还小时， // 说明我们还没为 t 找到合适的位置 // 继续我们的移动过程 // 当循环结束时，说明 t 有了合适的位置 // 将 t 赋值到 j 的位置 *__j = _VSTD::move(__t); } // 让 __j 指向新的末尾 __j = __i; } }
较大规模时的实现
那当排序长度大于 __limit 的时候，怎么处理呢？
_RandomAccessIterator __m = __first; _RandomAccessIterator __lm1 = __last; --__lm1; // last minus 1, 指向最后一个元素 unsigned __n_swaps; { difference_type __delta; if (__len >= 1000) { // 当需要排序的元素个数大于等于 1000 时 // 我们先将五等分点的元素进行排序（排序后仍在五等分点上） __delta = __len/2; __m += __delta; __delta /= 2; __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); // 此时在五等分点的五个元素是排好序的 } else { // 当需要排序的元素个数小于 1000 时 // 我们将三等分点的元素进行排序（排序后仍在三等分点上） __delta = __len/2; __m += __delta; __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); // 此时在三等分点的三个元素是排好序的 } } // __m 所指向的元素的值处于被选中的三个／五个元素的值中的中间 // 我们的目标是区间 [__first, __m) 的元素的值都小于 __m 所指向的元素的值，[__m, __last) 的元素的值都大于等于 __m 所指向的元素的值 _RandomAccessIterator __i = __first; _RandomAccessIterator __j = __lm1; // __m 所指向的元素的值一定小于等于 __lm1 所指向的元素的值 // 因为无论是 3 等分还是 5 等分，__m 和 __lm1 都参与了排序，且 __m 的位置在中间
因为我们的目标是区间 [__first, __m) 的元素的值都小于 __m 所指向的元素的值，[__m, __last) 的元素的值都大于等于 __m 所指向的元素的值，但是如果我们刚才选几个数时运气不太好，正好让 __first 所指向的元素的值等于 __m 所指向的元素的值的话，我们的第一个区间就空了，这就非常糟糕了。于是为了处理这个情况
if (!__comp(*__i, *__m)) // if *__first == *__m，如果 __first 所指向的元素的值等于 __m 所指向的元素的值 { // *__first == *__m, *__first doesn't go in first part // __first 所指向的元素的值等于 __m 所指向的元素的值, 于是 __first 所指向的元素不应该在第一个区间 // manually guard downward moving __j against __i // 手动让 __j 让 __i 靠近 while (true) { if (__i == --__j) { // *__first == *__m, *__m <= all other elements // __first 所指向的元素的值等于 __m 所指向的元素的值, __m 所指向的元素的值小于等于所有其他元素的值 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) // 重新划分为区间 [__first, __i) == __first 所指向的元素的值， 和 __first 所指向的元素的值小于区间 [__i, __last) 上任何元素的值 ++__i; // __first + 1 // __i 移动到 __first 所指的后一个元素（第二个） __j = __last; if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) // 如果__first 所指向的元素的值等于 __last-1 所指向的元素（即最后一个元素）的值 // 有可能全是相等的元素 // 从第二个（上方的++__i）开始依次与 __first 所指向的元素的值相比 { while (true) { if (__i == __j) // 如果 __i 已经指向了 __last // 说明全都是大小相等的元素 return; // [__first, __last) all equivalent elements if (__comp(*__first, *__i)) { // 如果 __first 小于某个 __i 指向的元素 // 说明这一组不全是相等的元素 // 我们的确可以重新划分 swap(*__i, *__j); ++__n_swaps; ++__i; break; } ++__i; } } // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 // [__first, __i) == *__first 且 *__first < [__j, __last) 且 __j == __last - 1 // 这说明第二个区间只有一个数，并且这个数大于第一区间所有的数 // 如果 __i 指向的和 __j 指向的是同一位置 if (__i == __j) // 那么两个区间可以合在一起，并且是排好序的 return; // 如果第一区间的右端和第二区间的左端不在同一位置 while (true) { // 将 __i 向后移动，直到 __first 指向的元素的值小于 __i 指向的元素的值 while (!__comp(*__first, *__i)) ++__i; // 将 __j 向前移动，直到 __first 指向的元素的值不再小于 __j 指向的元素的值 while (__comp(*__first, *--__j)) ; // 如果 __i 的位置大于等于 __j 的位置 // 说明两个区间发生了重叠，这意味着 // 第一区间上 __first 所指向的元素的值比某元素的值小 // 第二区间上某元素的值比 __first 所指向的元素的值小 if (__i >= __j) break; // 若两个区间没有交叉 // 则交换 __i 和 __j 所指向的元素的值 swap(*__i, *__j); ++__n_swaps; // 将 __i 向后移动一位 ++__i; } // [__first, __i) == *__first and *__first < [__i, __last) // The first part is sorted, sort the secod part // _VSTD::__sort<_Compare>(__i, __last, __comp); // 最后我们将得到这样的两个区间 // 第一个区间上的元素的值都相等，范围是 [__first, __i) // 第二个区间上的元素都有 __first 所指向的元素的值小于第二个区间上的任意元素 // 第二个区间的范围是[__i, __last) // 显然，我们只需要再对第二区间排序就可以了 // 直接重设开头的地址 __first = __i; // 然后重新开始 goto __restart; } // 这里是之前判断是否有 “__first 所指向的元素的值等于 __m 所指向的元素的值, __m 所指向的元素的值小于等于所有其他元素的值” 的地方 if (__comp(*__j, *__m)) { // 如果有一个元素小于 __m 所指的元素的值的话 // 则不会是那种情况 swap(*__i, *__j); ++__n_swaps; break; // found guard for downward moving __j, now use unguarded partition } } }
进行到这一步的时候，我们已经处理了如下情况
$$\begin{align}&&n\in[0, 5]\\
&&n\in(5, \_\_limit]\\
&1, 1, \dots , 1&\text{全相等}\\
&1, 1, \dots , 1, 2&\text{两边区间正好接在一起}\end{align}$$
后两种情况都是在 __first 所指向的元素的值与 __m 所指向的元素的值等于的情况下才有的，那么在不相等的时候呢？
// It is known that *__i < *__m // 此时有 __i 所指向的元素的值小于 __m 所指向的元素的值 // __i 的初值是 __first // __i 向后移动一位 ++__i; // j points beyond range to be tested, *__m is known to be <= *__lm1 // __m 所指向的元素的值必有小于等于 __lm1 所指向的元素的值（因为排序） // if not yet partitioned... // 如果还没有划分区间 if (__i < __j) { // known that *(__i - 1) < *__m // __i 的前一个元素的值小于 __m 所指向的元素的值 // known that __i <= __m // __i 的位置小于等于 __m 的位置 while (true) { // __m still guards upward moving __i // __m 的位置是 __i 移动的上界 // 因为当 __i 移动到 __m 的位置时，此循环条件必不成立 // 让 __i 向后移动，直到某个 __i 所指向的元素的值不再小于 __m 所指向的元素的 while (__comp(*__i, *__m)) ++__i; // It is now known that a guard exists for downward moving __j // 移动 __j 时，也有一个下界存在 // 让 __j 向前移动，直到某个 __j 所指向的元素的值小于 __m 所指向的元素的 while (!__comp(*--__j, *__m)) ; // 如果区间有交叉了，则跳出循环 if (__i > __j) break; // 否则交换 __i 和 __j 所指向的元素的值 swap(*__i, *__j); ++__n_swaps; // It is known that __m != __j // If __m just moved, follow it // 如果 __i 移动到了 __m 的位置 if (__m == __i) // 重新设置 __m 的位置 __m = __j; ++__i; } }
运行完上面那段之后，就会有区间 [__first, __i) 上都小于 __m 所指向的元素的值，以及 __m 所指向的元素的值小于等于区间 [__i, __last) 上任意元素的值，但是由于不清楚 __i 和 __m 的位置，所以我们还需要再稍微判断调整一下
// [__first, __i) < *__m and *__m <= [__i, __last) if (__i != __m && __comp(*__m, *__i)) { // 如果 __i 和 __m 不是在同一个位置 // 且 __m 所指向的元素的值比 __i 所指向的元素的值小 // 那么交换 __i 和 __m 所指向的元素的值 swap(*__i, *__m); ++__n_swaps; }
这样以来，我们就有了区间 [__first, __i) 上都小于 __i 所指向的元素的值，以及 __i 所指向的元素的值小于等于区间 [__i+1, __last) 上任意元素的值
现在，还记得我们一直记录的交换次数（__n_swaps）吗？
// If we were given a perfect partition, see if insertion sort is quick... // 如果我们现在有一个完美的划分，让我们试试插入排序是否够快 if (__n_swaps == 0) { // 如果一直没发生过交换的话 // 试试在 [__first, __i) 上进行不完全（限制插入次数）的插入排序 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) { // 如果在 [__i+1, __last) 上进行不完全插入排序能够很快排好的话 if (__fs) // 如果在 [__first, __i) 上进行不完全插入排序也能够很快排好的话 // 那么就排序完成 return; // 否则将末尾设置为 __i // 即再来处理 [__first, __i) 这一段 __last = __i; continue; } else { // 如果在 [__i+1, __last) 上进行不完全插入排序没有很快排好的话 // 即在 [__i+1, __last) 上插入次数达到限制 if (__fs) { // 但是在 [__first, __i) 上能够很快排好的话 // 设置排序起点为 ++__i // 即再来处理 [__i+1, __last) 这一段 __first = ++__i; continue; } } // 如果运行到了这里 // 说明 [__first, __i) 和 [__i+1, __last) 都不能很快排好 }
不完全的插入排序
上面代码中提到的不完全（限制插入次数）的插入排序是什么样的呢？
/// 不完全的插入排序 /// 限制了插入次数 template <class _Compare, class _RandomAccessIterator> bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 这里对 0 ~ 5 的元素个数处理与 __sort 里相同 switch (__last - __first) { case 0: case 1: return true; case 2: if (__comp(*--__last, *__first)) swap(*__first, *__last); return true; case 3: _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return true; case 4: _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return true; case 5: _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return true; } // 下面部分和之前提到的 __insertion_sort_3 基本相同 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); // 除了这里限制了最多有 8 个数插入之外 const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { if (__comp(*__i, *__j)) { value_type __t(_VSTD::move(*__i)); _RandomAccessIterator __k = __j; __j = __i; do { *__j = _VSTD::move(*__k); __j = __k; } while (__j != __first && __comp(__t, *--__k)); *__j = _VSTD::move(__t); // 这里是对限制的判断 if (++__count == __limit) // 如果 __i 是末尾的话 // 说明刚好在第 8 次插入时完成了排序 return ++__i == __last; } __j = __i; } return true; }
那么 [__first, __i) 和 [__i+1, __last) 都不能很快排好的话，我们就递归调用自己
// sort smaller range with recursive call and larger with tail recursion elimination // 对小的区间使用递归调用，对大的区间使用尾递归消除 if (__i - __first < __last - __i) { // 如果前一个区间的元素个数较少 // 递归调用排好前面的区间 _VSTD::__sort<_Compare>(__first, __i, __comp); // _VSTD::__sort<_Compare>(__i+1, __last, __comp); // 外层的 while 循环排序起点改到 __i+1 __first = ++__i; } else { // 如果后一个区间的元素个数较少 // 递归调用排好后面的区间 _VSTD::__sort<_Compare>(__i+1, __last, __comp); // _VSTD::__sort<_Compare>(__first, __i, __comp); // 外层的 while 循环排序终点改到 __i __last = __i; }
总结
LLVM 的 libcxx 中实现的 std::sort 的核心流程如下
procedure __sort(first, last, comp):
设置 limit 的大小
- 排序的类型是简单复制构造、简单复制赋值时，limit := 30
- 否则，limit := 6
while True:
更新排序长度 len := last - first
处理 0 ~ 5 [0, 5] 个元素的排序
- 0, 1直接返回
- 2 比较大小并交换（如果需要）
- 3 __sort3
- 4 利用 __sort3 排前三个，找第四个的位置
- 5 利用 __sort4 排前四个，找第五个的位置
返回
处理 6 ~ limit [6, limit] 个元素的排序
插入排序
返回
处理 (limit, +inf) 个元素的排序
如果个数大于等于 1000，将五等分点的五个数原地排序
否则将三等分点的三个数原地排序
// 目标是 [__first, __m) 的元素的值都小于 __m 所指向的元素的值，[__m, __last) 的元素的值都大于等于 __m 所指向的元素的值
如果 *__first == *__m
考虑全部相等的情况
全部相等，返回
考虑可以分成两个区间，其中第一个区间全部相等并等于 *__first，而第二个区间只有一个数
返回
考虑可以分成两个区间，[__first, __i) == *__first and *__first < [__i, __last)
通过设置__first := __i，排序 [__i, __last)
如果 *__first < *__m
调整到 [__first, __i) < *__i and *__i <= [__i+1, __last)
如果没发生过交换，可能是只有个别没排好，试着对两个区间使用限制插入次数的插入排序
如果第一区间排好了 且 第二区间也排好了
返回
如果第一区间排好了 但 第二区间没排好
处理 [__i+1, __last)
如果第二区间排好了 但 第一区间没排好
处理 [__first, __i)
如果第一区间没排好 且 第二区间没排好
找出元素个数较少的那个区间
递归调用自己
更改排序范围
// 之后会回到外层的 while，尾递归消除
附带注释的 std::sort
// sort // stable, 2-3 compares, 0-2 swaps /// 当只有3个元素时的排序函数 /// 2到3次比较，0到2次交换 /// __libcxx_sort3执行完时，x <= y <= z template <class _Compare, class _ForwardIterator> unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) { unsigned __r = 0; // 下面所有的x,y,z若没有指明 // 则均是运行到那一步时，x,y,z的值（可能经过值交换） if (!__c(*__y, *__x)) { // 如果x <= y if (!__c(*__z, *__y)) { // 如果y <= z return __r; // 根据传递性，得到情况0，x <= y && y <= z } // 如果上面没有返回的话 // 说明 x <= y && y > z swap(*__y, *__z); // 交换 y 和 z // 此时 x <= z && y < z __r = 1; // 情况1，x <= z && y < z // 需要再次比较 x 和 y if (__c(*__y, *__x)) { // 如果 x > y swap(*__x, *__y); // 交换 x 和 y __r = 2; // 此时 x < y && y <= z } return __r; } // 已经知道x > y后 if (__c(*__z, *__y)) { // 如果 y > z // 那么传入时的大小顺序是 x > y > z // 我们排序的目标是 x < y < z swap(*__x, *__z); // 于是交换 x 和 z __r = 1; return __r; } // x > y, y <= z swap(*__x, *__y); // 交换 x 和 y // 此时 y > x, x <= z __r = 1; if (__c(*__z, *__y)) { // 如果 y > z swap(*__y, *__z); // 交换 y 和 z // 此时 z > y 且 z > x, x <= y __r = 2; } return __r; } // x <= y && y <= z // stable, 3-6 compares, 0-5 swaps /// 当只有4个元素时的排序函数 /// 3到6次比较，0到5次交换 /// __sort4执行完时，x1 <= x2 <= x3 <= x4 template <class _Compare, class _ForwardIterator> unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) { // 先利用__sort3 将 x1, x2, x3 排好序 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); // 此时有 x1 <= x2 <= x3 // 接下来找好 x4 的位置 if (__c(*__x4, *__x3)) { // 如果 x4 < x3 // 交换 x3 和 x4 swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { // 如果 x3 < x2 // 交换 x2 和 x3 swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { // 如果 x2 < x1 // 交换 x1 和 x2 swap(*__x1, *__x2); ++__r; } } } return __r; } // stable, 4-10 compares, 0-9 swaps /// 当只有5个元素时的排序函数 /// 4到10次比较，0到9次交换 /// __sort5执行完时，x1 <= x2 <= x3 <= x4 <= x5 template <class _Compare, class _ForwardIterator> unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { // 先将 x1, x2, x3, x4 排好序 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); // 此时有 x1 <= x2 <= x3 <= x4 // 接下来找好 x5 的位置 if (__c(*__x5, *__x4)) { // 如果 x5 < x4 // 交换 x4 和 x5 swap(*__x4, *__x5); ++__r; if (__c(*__x4, *__x3)) { // 如果 x4 < x3 // 交换 x3 和 x4 swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { // 如果 x3 < x2 // 交换 x2 和 x3 swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { // 如果 x2 < x1 // 交换 x1 和 x2 swap(*__x1, *__x2); ++__r; } } } } return __r; } template <class _Compare, class _RandomAccessIterator> void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 定义迭代器里面所用的值类型 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; // 先将传入的前三个排好序 _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); // 为已经排好序的部分的后一个元素 i 找位置 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { // 将 __i 所指向的元素与已经排好的最后那个比较 if (__comp(*__i, *__j)) { // 若 __i 所指向的元素小于排好序的最后那个元素 // 则说明需要把这第 i 个插入到已经排好序的里面 // 将 __i 所指向的元素保存到临时变量 t 里 value_type __t(_VSTD::move(*__i)); // 然后将把排好序部分，从尾到头，一个一个向后移动 // 直到 t 正好大于某个数 或者 到了头的时候 停止 // 使用 __k 来每次做比较 _RandomAccessIterator __k = __j; // 使用 __j 来作为每次赋值的位置 __j = __i; do { // 将 __k 指向的元素的值赋值到 __j 指向的位置上 *__j = _VSTD::move(*__k); // 更新 __j 指向的位置 __j = __k; } while (__j != __first && __comp(__t, *--__k)); // 若 __j 还不是第一个位置 // (__k 移动到 __k 的前一个位置之后)，t 的值比 __k 的值还小时， // 说明我们还没为 t 找到合适的位置 // 继续我们的移动过程 // 当循环结束时，说明 t 有了合适的位置 // 将 t 赋值到 j 的位置 *__j = _VSTD::move(__t); } // 让 __j 指向新的末尾 __j = __i; } } /// 不完全的插入排序 /// 限制了插入次数 template <class _Compare, class _RandomAccessIterator> bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 这里对 0 ~ 5 的元素个数处理与 __sort 里相同 switch (__last - __first) { case 0: case 1: return true; case 2: if (__comp(*--__last, *__first)) swap(*__first, *__last); return true; case 3: _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return true; case 4: _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return true; case 5: _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return true; } // 下面部分和之前提到的 __insertion_sort_3 基本相同 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); // 除了这里限制了最多有 8 个数插入之外 const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { if (__comp(*__i, *__j)) { value_type __t(_VSTD::move(*__i)); _RandomAccessIterator __k = __j; __j = __i; do { *__j = _VSTD::move(*__k); __j = __k; } while (__j != __first && __comp(__t, *--__k)); *__j = _VSTD::move(__t); // 这里是对限制的判断 if (++__count == __limit) // 如果 __i 是末尾的话 // 说明刚好在第 8 次插入时完成了排序 return ++__i == __last; } __j = __i; } return true; } /// 具体实现的函数 /// _RandomAccessIterator 支持随机访问的迭代器 /// _Compare 比较函数的类型 /// __first 需要排序的开始的地方 /// __last 需要排序的结束的地方 /// __comp 比较函数 template <class _Compare, class _RandomAccessIterator> void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // _Compare is known to be a reference type // 使用 type_traits 中提供的 std::iterator_traits 获得差值类型 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; // 迭代器本身指向的元素的类型 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; // 检查迭代器中的使用的类是否有简单复制构造函数 // copy constructible type （可复制构造类型）的含义很简单，如果一个类型有显式或隐式的复制构造函数，那么就是可复制构造的 // Checks whether a type is CopyConstructible, i.e. has an accessible explicit or implicit copy constructor. If the requirement is met, a member constant value equal true is provided, otherwise value is false. // http://en.cppreference.com/w/cpp/types/is_copy_constructible // http://www.cplusplus.com/reference/type_traits/is_trivially_copy_constructible/ // trivially copy constructible type（简单复制构造函数) 是指一个可以通过同类型的值或者引用构造的类型。标量类型，可以简单复制构造的类 和 数组 都是这种类型。 // A trivially copy constructible type is a type which can be trivially constructed from a value or reference of the same type. This includes scalar types, trivially copy constructible classes and arrays of such types. // 简单复制构造的类是这样一种类（它通过class, struct, union关键字定义）： // - 使用隐式定义的复制构造函数 // - 没有virtual成员 // - 它的基类和非静态数据成员（如果有的话），也必须是简单复制构造的 // A trivially copy constructible class is a class (defined with class, struct or union) that: // uses the implicitly defined copy constructor. // has no virtual members. // its base class and non-static data members (if any) are themselves also trivially copy constructible types. // 下一个条件，is_trivially_copy_assignable // 与上面的类似，如果说一个类型是copy assignable的话，那么它有显式或隐式的复制赋值函数 // 如果说一个类型是 trivially copy assignable的话，那么 // - 使用隐式定义的复制赋值函数 // - 没有virtual成员 // - 它的基类和非静态数据成员（如果有的话），也必须是简单复制赋值的 constdifference_type __limit = is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6; while (true) { __restart: // 需要排序的元素的长度 difference_type __len = __last - __first; // 处理长度为 0 到 5 时的排序 switch (__len) { // 长度为 0 或 1 时就无需排序了 case 0: case 1: return; case 2: // 只有2个元素时，直接比较并交换（如果需要交换的话） if (__comp(*--__last, *__first)) swap(*__first, *__last); return; case 3: // 只有3个元素时，同样直接比较并交换（不过加了一层函数调用，稍后分析） _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return; case 4: // 只有4个元素时，同上 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return; case 5: // 只有5个元素时，同上 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return; } // 如果排序长度小于限制时 // - 当元素是 简单复制构造 且 简单复制赋值 时，限制是 30 // - 否则限制是 6 if (__len <= __limit) { _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); return; } // __len > 5 // * __len > __limit * _RandomAccessIterator __m = __first; _RandomAccessIterator __lm1 = __last; --__lm1; // last minus 1, 指向最后一个元素 unsigned __n_swaps; { difference_type __delta; if (__len >= 1000) { // 当需要排序的元素个数大于等于 1000 时 // 我们先将五等分点的元素进行排序（排序后仍在五等分点上） __delta = __len/2; __m += __delta; __delta /= 2; __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); // 此时在五等分点的五个元素是排好序的 } else { // 当需要排序的元素个数小于 1000 时 // 我们将三等分点的元素进行排序（排序后仍在三等分点上） __delta = __len/2; __m += __delta; __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); // 此时在三等分点的三个元素是排好序的 } } // *__m is median // partition [__first, __m) < *__m and *__m <= [__m, __last) // (this inhibits tossing elements equivalent to __m around unnecessarily) // __m 所指向的元素的值处于被选中的三个／五个元素的值中的中间 // 我们的目标是区间 [__first, __m) 的元素的值都小于 __m 所指向的元素的值，[__m, __last) 的元素的值都大于等于 __m 所指向的元素的值 _RandomAccessIterator __i = __first; _RandomAccessIterator __j = __lm1; // j points beyond range to be tested, *__m is known to be <= *__lm1 // The search going up is known to be guarded but the search coming down isn't. // Prime the downward search with a guard. // __m 所指向的元素的值一定小于等于 __lm1 所指向的元素的值 // 因为无论是 3 等分还是 5 等分，__m 和 __lm1 都参与了排序，且 __m 的位置在中间 if (!__comp(*__i, *__m)) // if *__first == *__m, 如果 __first 所指向的元素的值等于 __m 所指向的元素的值 { // *__first == *__m, *__first doesn't go in first part // __first 所指向的元素的值等于 __m 所指向的元素的值, 于是 __first 所指向的元素不应该在第一个区间 // manually guard downward moving __j against __i // 手动让 __j 让 __i 靠近 while (true) { if (__i == --__j) { // *__first == *__m, *__m <= all other elements // __first 所指向的元素的值等于 __m 所指向的元素的值, __m 所指向的元素的值小于等于所有其他元素的值 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) // 重新划分为区间 [__first, __i) == __first 所指向的元素的值， 和 __first 所指向的元素的值小于区间 [__i, __last) 上任何元素的值 ++__i; // __first + 1 // __i 移动到 __first 所指的后一个元素（第二个） __j = __last; if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) // 如果__first 所指向的元素的值等于 __last-1 所指向的元素（即最后一个元素）的值 // 有可能全是相等的元素 // 从第二个（上方的++__i）开始依次与 __first 所指向的元素的值相比 { while (true) { if (__i == __j) // 如果 __i 已经指向了 __last // 说明全都是大小相等的元素 return; // [__first, __last) all equivalent elements if (__comp(*__first, *__i)) { // 如果 __first 小于某个 __i 指向的元素 // 说明这一组不全是相等的元素 // 我们的确可以重新划分 swap(*__i, *__j); ++__n_swaps; ++__i; break; } ++__i; } } // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 // [__first, __i) == *__first 且 *__first < [__j, __last) 且 __j == __last - 1 // 这说明第二个区间只有一个数，并且这个数大于第一区间所有的数 // 如果 __i 指向的和 __j 指向的是同一位置 if (__i == __j) // 那么两个区间可以合在一起，并且是排好序的 return; // 如果第一区间的右端和第二区间的左端不在同一位置 while (true) { // 将 __i 向后移动，直到 __first 指向的元素的值小于 __i 指向的元素的值 while (!__comp(*__first, *__i)) ++__i; // 将 __j 向前移动，直到 __first 指向的元素的值不再小于 __j 指向的元素的值 while (__comp(*__first, *--__j)) ; // 如果 __i 的位置大于等于 __j 的位置 // 说明两个区间发生了重叠，这意味着 // 第一区间上 __first 所指向的元素的值比某元素的值小 // 第二区间上某元素的值比 __first 所指向的元素的值小 if (__i >= __j) break; // 若两个区间没有交叉 // 则交换 __i 和 __j 所指向的元素的值 swap(*__i, *__j); ++__n_swaps; // 将 __i 向后移动一位 ++__i; } // [__first, __i) == *__first and *__first < [__i, __last) // The first part is sorted, sort the secod part // _VSTD::__sort<_Compare>(__i, __last, __comp); // 最后我们将得到这样的两个区间 // 第一个区间上的元素的值都相等，范围是 [__first, __i) // 第二个区间上的元素都有 __first 所指向的元素的值小于第二个区间上的任意元素 // 第二个区间的范围是[__i, __last) // 显然，我们只需要再对第二区间排序就可以了 // 直接重设开头的地址 __first = __i; // 然后重新开始 goto __restart; } // 这里是之前判断是否有 “__first 所指向的元素的值等于 __m 所指向的元素的值, __m 所指向的元素的值小于等于所有其他元素的值” 的地方 if (__comp(*__j, *__m)) { // 如果有一个元素小于 __m 所指的元素的值的话 // 则不会是那种情况 swap(*__i, *__j); ++__n_swaps; break; // found guard for downward moving __j, now use unguarded partition } } } // It is known that *__i < *__m // 此时有 __i 所指向的元素的值小于 __m 所指向的元素的值 // __i 的初值是 __first // __i 向后移动一位 ++__i; // j points beyond range to be tested, *__m is known to be <= *__lm1 // __m 所指向的元素的值必有小于等于 __lm1 所指向的元素的值（因为排序） // if not yet partitioned... // 如果还没有划分区间 if (__i < __j) { // known that *(__i - 1) < *__m // __i 的前一个元素的值小于 __m 所指向的元素的值 // known that __i <= __m // __i 的位置小于等于 __m 的位置 while (true) { // __m still guards upward moving __i // __m 的位置是 __i 移动的上界 // 因为当 __i 移动到 __m 的位置时，此循环条件必不成立 // 让 __i 向后移动，直到某个 __i 所指向的元素的值不再小于 __m 所指向的元素的 while (__comp(*__i, *__m)) ++__i; // It is now known that a guard exists for downward moving __j // 移动 __j 时，也有一个下界存在 // 让 __j 向前移动，直到某个 __j 所指向的元素的值小于 __m 所指向的元素的 while (!__comp(*--__j, *__m)) ; // 如果区间有交叉了，则跳出循环 if (__i > __j) break; // 否则交换 __i 和 __j 所指向的元素的值 swap(*__i, *__j); ++__n_swaps; // It is known that __m != __j // If __m just moved, follow it // 如果 __i 移动到了 __m 的位置 if (__m == __i) // 重新设置 __m 的位置 __m = __j; ++__i; } } // [__first, __i) < *__m and *__m <= [__i, __last) if (__i != __m && __comp(*__m, *__i)) { // 如果 __i 和 __m 不是在同一个位置 // 且 __m 所指向的元素的值比 __i 所指向的元素的值小 // 那么交换 __i 和 __m 所指向的元素的值 swap(*__i, *__m); ++__n_swaps; } // [__first, __i) < *__i and *__i <= [__i+1, __last) // If we were given a perfect partition, see if insertion sort is quick... // 如果我们现在有一个完美的划分，让我们试试插入排序是否够快 if (__n_swaps == 0) { // 如果一直没发生过交换的话 // 试试在 [__first, __i) 上进行不完全（限制插入次数）的插入排序 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) { // 如果在 [__i+1, __last) 上进行不完全插入排序能够很快排好的话 if (__fs) // 如果在 [__first, __i) 上进行不完全插入排序也能够很快排好的话 // 那么就排序完成 return; // 否则将末尾设置为 __i // 即再来处理 [__first, __i) 这一段 __last = __i; continue; } else { // 如果在 [__i+1, __last) 上进行不完全插入排序没有很快排好的话 // 即在 [__i+1, __last) 上插入次数达到限制 if (__fs) { // 但是在 [__first, __i) 上能够很快排好的话 // 设置排序起点为 ++__i // 即再来处理 [__i+1, __last) 这一段 __first = ++__i; continue; } } // 如果运行到了这里 // 说明 [__first, __i) 和 [__i+1, __last) 都不能很快排好 } // sort smaller range with recursive call and larger with tail recursion elimination // 对小的区间使用递归调用，对大的区间使用尾递归消除 if (__i - __first < __last - __i) { // 如果前一个区间的元素个数较少 // 递归调用排好前面的区间 _VSTD::__sort<_Compare>(__first, __i, __comp); // _VSTD::__sort<_Compare>(__i+1, __last, __comp); // 外层的 while 循环排序起点改到 __i+1 __first = ++__i; } else { // 如果后一个区间的元素个数较少 // 递归调用排好后面的区间 _VSTD::__sort<_Compare>(__i+1, __last, __comp); // _VSTD::__sort<_Compare>(__first, __i, __comp); // 外层的 while 循环排序终点改到 __i __last = __i; } } } // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare template <class _RandomAccessIterator, class _Compare> inline_LIBCPP_INLINE_VISIBILITY void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { #ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __sort<_Comp_ref>(__first, __last, __c); #else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sort<_Comp_ref>(__first, __last, __comp); #endif // _LIBCPP_DEBUG }
一堆一堆的下划线看起来真是太费劲了。。。
受益匪浅喵~
呜哇，还请多多指教(｡･ω･｡)
呜喵
晚上好喵~
两年不碰C++风格的语言之后……
看着代码感觉好陌生
（于是，当我阅读以前写的代码时，总觉得，现在的我不如过去的我）
QuQ
当我看到以前在 OI 队写的代码时，也有这样的体会……QAQ