浅析sort

# 0.前言 相信每个入门的同学都见过这样一个题目： > 给定一些整数，将它们从小到大排序后输出 同学们常常会写这样的代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,a[1000010]; int main() { scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i=1;i<n;++i)printf("%d ",a[i]); printf("%d\n",a[n]); return 0; } ``` 这里的`sort`就是我们今天的主角 别看它语句短小，但却无比精悍 $upd:2019.8.28\ 19:22$ 更新$2.1$部分，增添了"还是//3"一项 $upd:2019.10.17\ 22:13$ 想卡掉`sort`的是魔鬼吧（然而还是可以的，尽管并不会卡），那个说是补充的并看不懂感觉这篇文章好理解一些吧，背景的话看这里([$Link$](https://cdn.luogu.com.cn/upload/image_hosting/bx60su5w.png)）（我战兔最帅了）还有能不能不要老是复读我的话啊？~~虽然人类的本质是复读机~~ # 1.观察 首先，观察`sort`的来源（我这里使用了`VSCode`的速览定义功能） 观察到它包含在`stl_algo.h`文件中（这一文件包含在`algorithm`头文件中） 找到其定义为 ```cpp 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); //start if (__first != __last) { std::__introsort_loop(__first, __last, std::__lg(__last - __first) * 2); std::__final_insertion_sort(__first, __last); } //end }//这里吐槽一下C++ STL编写者的码风 ``` 看到变量是`_RandomAccessIterator`（即随机迭代器） 这是个什么东西鸭？其实就是数组、`vector`、`deque`这类东西的实现方法 接下来观察到其主体代码是从`//start`到`//end`的部分，前面可以不管 # 2.深入分析 ## 2.1 __introsort_loop 这是个什么玩意？  ```cpp template<typename _RandomAccessIterator, typename _Size, typename _Compare> void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp) { while (__last - __first > int(_S_threshold))//5 { if (__depth_limit == 0) { _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);//4 return; } //1 --__depth_limit; _RandomAccessIterator __cut = std::__unguarded_partition_pivot(__first, __last, __comp);//3 std::__introsort_loop(__cut, __last, __depth_limit, __comp); __last = __cut; //2 } } ``` 如上是其源码，发现它是一个递归结构 ### 2.1.1 //1到//2 不难看出`//1`与`//2`之间正是快速排序实现 然而……貌似它只处理了右区间部分？左区间怎么办呢？ 别急，我们来重新浏览一下： 它在排完序之后把`cut`的值付给了`last` 然后由于它是循环，所以……下一次就是处理左区间了 所以它相比于我们所写的排序优点正是此处 巧妙地将递归换成了循环，虽然复杂度不变，但常数就是大幅提升了 这似乎从一方面解释了`sort`比手写排序快的原因（借用一个图）：  ### 2.1.2 //3 不过这并不能让快排避免退化的危机，只能解决常数问题 然而`sort`似乎基本没有退化过，这是为什么呢？ 首先注意`//3`处（`pivot`就是常说的哨兵） 这里的哨兵并没有使用`start`，`last`，中部中的任何一个 通过持续跟踪，发现哨兵使用的是三者的中值 这就从一定程度上优化了算法 ### 2.1.3 还是//3 老样子，直接上这一部分的源码： ```cpp template<typename _RandomAccessIterator, typename _Compare> inline _RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { _RandomAccessIterator __mid = __first + (__last - __first) / 2; std::__move_median_first(__first, __mid, (__last - 1), __comp); return std::__unguarded_partition(__first + 1, __last, *__first, __comp); } ``` `__move_median_first`是用来将三者从小到大排序 `__unguarded_partition`而不断去交换位置错误的元素，直到first和last指针无有效区域为止 它并不会去做任何一次比较运算（这一点在下文$2.2.2$中也有提及） 那么，为什么能不比较呢？ 它由于$2.1.2$的保证（即使用三者的中值），可以得出一定会在超出有效区域之前中止 也就是说，它可以保证不需要比较，可以自动操作，不必考虑越界问题 不比较，又可以进行一定的常数优化 减少常数、运算次数，就是`STL`编写者的唯一目的 ~~（所以连码风都不管了）~~ 这一算法被称之为分割算法（即原版本说的没看懂的部分，也是对$2.1.2$的一些补充） ### 2.1.4 //4 这个`partial_sort`是什么？为什么要用它？ 通过调查源码，发现这个`partial_sort`就是堆排：  那么`depth_limit`是什么？有何作用？ 回到`sort`本体，发现`depth_limit`即$\log_2(last-first)$（亦即$\log_2n$） 如果递归次数到达$\log_2n$会怎么样？ **退化**，在退化之际使用堆排来弥补，可以基本解决退化 这也正是`sort`不退化的奥秘所在 ## 2.2 __final_insertion_sort 这……终极插入排序？（雾） 前面不是排好了么？要它何用？ 等等，回到$2.1$的`//5`处，这个`_S_threshold`是？ 查阅定义得，`_S_threshold`为$16$，一个常数？ 所以说……快排剩了最前面$16$个不排，交给插入排序？ 理论上就算退化复杂度也才相当于插入排序啊，为什么呢？ 这时就需要复习一下插排的概念了 ### 2.2.1 插排复习 插排原理：每一个元素通过比较，找到应插入位置 其特点：**最好情况（基本有序）复杂度**$O(n)$ 这样就可以理解了，快排保证了前$16$个元素基本有序，但非完全有序 所以，这样只要$O(n)$就可以排好最左边$16$个 ### 2.2.2 分析 以为这就结束了？想的太简单了  观察`__final_insertion_sort`源码： ```cpp template<typename _RandomAccessIterator, typename _Compare> void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { if (__last - __first > int(_S_threshold)) { std::__insertion_sort(__first, __first + int(_S_threshold), __comp); std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, __comp); } else std::__insertion_sort(__first, __last, __comp); } ``` 可以看到，又调用了两个插入排序，它们分别的代码： ```cpp template<typename _RandomAccessIterator, typename _Compare> void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { if (__first == __last) return; for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) { if (__comp(*__i, *__first)) { typename iterator_traits<_RandomAccessIterator>::value_type __val = _GLIBCXX_MOVE(*__i); _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); *__first = _GLIBCXX_MOVE(__val); } else std::__unguarded_linear_insert(__i, __comp); } } ``` ```cpp template<typename _RandomAccessIterator, typename _Compare> inline void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; for (_RandomAccessIterator __i = __first; __i != __last; ++__i) std::__unguarded_linear_insert(__i, __comp); } ``` ~~此时此刻，您的内心一定是崩溃的~~ 这里就不贴`__unguarded_linear_insert`的代码了，只需要知道其作用 其作用是找到应插入的位置并插入（无底洞啊，不建议自己查看） 而如果，当前值要插在前头，直接让其他的后移 理论上和普通插排毫无区别~~实际也是~~，但是略微对常数有所优化 那`__unguarded_insertion_sort`与`__insertion_sort`有何区别？又有什么用？ 貌似是省去了`if`的判断句？ 仅此而已？！ 对，仅此而已。 但是为什么可以去掉呢？ 因为这一排序是**建立在最左边永远是最小值**的基础上的 不仅是`__unguarded_insertion_sort`、`__unguarded_partition`，事实上，所有的以`__unguarded`开头的函数 **都不会考虑越界！** 而众所周知，比较函数是很耗时的，因此常数会有较大提升 ### 2.2.3 效率 我们从各种操作入手分析 首先，经典插排，$2N$次比较，$3N$次赋值，$N$次减法，$N$次自减。 其次，`__insertion_sort` 分两种情况： 每次第一分支，即`if`语句执行情况，$N+1$次比较，$N+1$次赋值，$3N$次自减/加（注意：此处$+1$这类常数不可忽略） 每次第二分支，即`else`语句执行情况，$N+1$次比较，$2N$次赋值，$N$次自减 那么假设二者出现概率相同，则平均为$N+1$次比较，$1.5N+0.5$次赋值，$2N$次自减 可以看到，少了$N-1$次比较，$1.5N-0.5$次赋值，$N$次减法，多了$N$次自减 而且，已知比较时间开销很大，赋值小一些，而减法、自减基本不耗时 而`__unguarded_insertion_sort`则是$N$次比较，$2N$次赋值和$N$次自减（与每次第二分支时间复杂度基本相同） 不过，在$N$很大时，$+1$的常数也会很大，这也是一直没有省略的原因 （以上复杂度请自行证明） ~~您：……看个文章还要自证？？？~~ ### 2.2.4 其他 既然`__unguarded_insertion_sort`的时间要小得多，那么为什么不直接用呢？ 不知道读者有没有注意到2.2.2最后有一行加粗的字体 这一行字解释了为什么不能直接用`__unguarded_insertion_sort`排序 等等，如何保证在`__insertion_sort`后，**全局最小值**在左边呢？ 先回到`__introsort_loop`，它在什么情况下会返回呢？ 一是区域小于等于16（即`_S_threshold`），二是超过`depth_limit`，也就是$\log_2n$ 而由快排定义可知，左边区间的所有数据一定比右边小（也可参考图）：  所以，如果是第一种情况，就可以得出最小值在左边 如果是第二种情况，那么最左边的区间会调用堆排序，所以这段区间的最小值一定位于最左端。再加上左边区间所有的数据一定比右边小，那么最左边的数据一定是全局最小值 # 3.其他 至此，我们完成了对`sort`的初步探究（仅是初步） 那么，是不是所有容器都能使用`sort`呢？ 并不是，主要有`vector`、`list`、数组可以使用 `unordered_`开头的容器只有前向迭代器，然而在1中已经说过，只有随机迭代器才能使用`sort` 而，`map`、`set`、`priority_queue`这类自带排序的当然是用不了了 而`queue`、`stack`这类则因为它们对出口和入口做了限制，无法排序 那`list`呢？它的迭代器是双向迭代器，也不行 不过不必担心，众所周知，`list`自带`list::sort`，虽然不能用`std`，但可以自己使用 万万没想到啊，一个小小的`sort`居然有这么多优化 不得不说，`C++ STL`编写者真的把编译器的效率压榨了不少，真是视效率如生命啊！ 试问：有多少人能够自己写出像`STL`这样好的库？ 这正是C++优点所在（并未引战） 什么？平板电视？反正平板电视也没`sort` 这倒是让我想起一个东西：[平方根倒数速算法](https://baike.baidu.com/item/平方根倒数速算法/4075273) ~~下一个迫害来源，万♂恶♂之♂源~~