0.前言

相信每个入门的同学都见过这样一个题目：

给定一些整数，将它们从小到大排序后输出

同学们常常会写这样的代码：

#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.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源码：

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);
    }

可以看到，又调用了两个插入排序，它们分别的代码：

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);
    }
    }

 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

这倒是让我想起一个东西：平方根倒数速算法

下一个迫害来源，万♂恶♂之♂源