[C++][标准库源码] sort ———— 性能极致的排序算法

C++

发布日期: 2022-05-01

更新日期: 2022-06-01

文章字数: 2.1k

阅读时长: 8 分

写在前面

std::sort 的实现基于 David Musser 1996年提出的一种混合式排序算法 Introspective Sorting，即IntroSort，其行为几乎与median-of-three QuickSort完全相同，但是当Partition有恶化的倾向时，能够自我侦测，转而改用HeapSort，使复杂度维持在HeapSort的 O(NlonN)。

—— 侯捷《STL源码剖析》

《STL源码剖析》这本书历史悠久，至今已有20年历史。不过20年时间在C++的历史长河中算不了什么。20年过去，GCC C++ STL 大部分算法、数据结构的实现和SGI STL基本相同。所以，侯捷20年前对于 std::sort 的描述依然适用，书中对 std::sort 源码的剖析依然准确。如果想从头了解 std::sort ，可以去看这本书；这里我的侧重点与《STL源码剖析》中不同，更关注一些细节和trick。

摘要

introsort，大体框架上遵循传统的快排算法，在极端情况下转为堆排序；std::sort在最后，会在整个数组上做一次插入排序。
introsort在GCC源码中涉及了两处以__unguarded__...... 为名的函数，它们的名字暗示了它们不会做越界检查，已达到更快的速度。本文特地分析了这两个函数，尤其是它们不做越界检查的情况下，如何避免越界。
在快排中 pivot的选择是一件non-trivial的事情，introsort选用了median-of-three方法，这又与一个 __unguarded 函数产生了联动。
在源码中，插入排序有两种实现，它们有什么区别？

代码分析

所代码来自 gcc stl_algo.h，建议搭配源码阅读。

std::sort 进行如下两步

__introsort_loop(__first, __last, __lg(__last - __first) * 2); 第三个参数中的__lg 为 $log_2$，该参数用于控制快排的递归层数；例如，当数组长度为1024时，__lg(1024) * 2为 20，即最多递归20层。如果递归层数过深，那么很容易趋向最坏时间复杂度 $O(n^2)$。
__final_insertion_sort(__first, __last) ：对整个数组做一次插入排序。一般情况下，插入排序的复杂度为 $O(n^2)$。不过，由于 __introsort_loop 在区间不大于 16 时停止排序，此时，整个序列呈现整体有序，局部乱序的结果；也就是说，每个子序列里的数一定大于等于前一个子序列中任何数。在这种情况下，插入排序的时间复杂度并不高。

`__introsort_loop`

该函数和传统的QuickSort具有类似的框架，只是细节上有一些不同。

如果区间长度大于 S_threshold( = 16)，则：

如果depth_limit == 0，则转为堆排序 __partial_sort。

这意味着尽管通过median-of-three选择了较优的pivot，但是左右子数组仍然不平衡，趋向于最坏复杂度 $O(N^2)$。这意味着快排在这个数组上不适用，于是转而使用堆排序。
调用__unguarded_partition_pivot ，进行choice of pivot和partition。
- choice of pivot：快排的时间复杂度度与pivot的选择息息相关，最简单的办法是选择区间的第一个元素，但是，如果待排序数组为有序数组，那么时间复杂度会退化至 $O(N^2)$。其他方法包括 random pivot， median-of-three等。但是，选择Pivot的复杂度需要严格控制，过于复杂的规则会引入较高的overhead，反而导致时间复杂度升高。
  
  关于pivot的选择，是个经过了非常深入研究的问题，可以参考[1]，[1]表明random pivot的平均复杂度约为$1.385nlogn$ ，而median-of-three的复杂度约为 $1.188nlogn$。对于特别大的数组，ninther rule更适用，它是median-of-three的递归形式，尽管这引入了更大的overhead，但是对于足够大的数组，这一点overhead影响不大。
  
  gcc中使用的是”median-of-three“，
  
  median-of-three并不是完美的方法，[3]中构造了一种特别的数组针对该方法。
- Partition：Partition由__unguarded_partition 实现，
```
while (true)
	{
	  while (__comp(__first, __pivot)) //不会判断 first <= last
	    ++__first;
	  --__last;
	  while (__comp(__pivot, __last)) //同上
	    --__last;
	  if (!(__first < __last))
	    return __first;
	  std::iter_swap(__first, __last);
	  ++__first;
	}
```
它的操作与一般的快排基本一致。唯一的区别是，循环时不会判断 first <= last，但这并不会导致越界。

这是因为之前使用了median-of-three，所以数组中至少有一个元素大于或等于pivot，所以 while (__comp(__first, __pivot))一定会在某个元素处停止，一定不会越界。这为代码减少了2处越界条件判断，略微提升了速度。
经常会有这么一种bug，如果__comp 仿函数存在错误，可能会导致越界[2]，比如：
```
std::vector<int> values{6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6};
std::sort(values.begin(), values.end(), [](int v1, int v2){
return v1 >= v2;
});
```
试试看

这就是__unguarded_partition不做越界检查导致的。

将右半部分进行递归，继续调用 __introsort_loop。
将左半部分进行循环。传统的快排中，会将左右部分分别进行递归快排，gcc中为了省去递归函数调用时所产生的开销，省去了左半部分的递归，改用循环处理。

这种写法可读性较差，但效率并不比两次递归更好。—— 《STL源码剖析》

如果序列长度 <= 16，则返回，等待最后的插入排序处理。因为快排对于小的数据量并不划算，快排产生的多次递归调用开销导致其速度甚至不如插入排序。

`__final_insertion_sort`

这个部分主要包含两个函数 __insertion_sort 和 __unguarded_linear_sort。

他们都是插入排序，区别在于：

__unguarded_linear_sort需要传入的数组的前方存在一个较小或相等的值，像一个guard一样，阻止循环越界。
__insertion_sort 不需要任何要求，可以接受任何数组；

`__unguarded_linear_sort`

插入排序维护两个部分，已排序、未排序部分。它包含两重循环，每次外部循环将当前数插入到已排序部分合适的位置。

__unguarded_insertion_sort 了实现外层循环，内层循环（即插入）调用了函数 __unguarded_linear_insert完成。

__unguarded_linear_insert 该函数用于寻找合适的位置并插入。它的核心代码如下：

 __unguarded_linear_insert(_RandomAccessIterator __last,
	      _Compare __comp)
  {
__val = _GLIBCXX_MOVE(*__last);
   	 _RandomAccessIterator __next = __last;
    	--__next;
    	while (__comp(__val, __next) /* 缺少：&& __next >= __first */) //可能越界
      {
        *__last = _GLIBCXX_MOVE(*__next);
        __last = __next;
        --__next;
      }
    	*__last = _GLIBCXX_MOVE(__val);
  }

可以看到，这个函数完全不关注 __first，根本不考虑 __next 是否可能越界。所以，__unguarded_linear_insert的调用者需要保证，__last之前必须存在一个数小于等于 *__last，使得while循环终止。间接的，__unguarded_linear_sort 的调用者也需要保证这点。

`__insertion_sort`

__insertion_sort(_RandomAccessIterator __first,
   _RandomAccessIterator __last, _Compare __comp)
{
    if (__first == __last) return;

    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
    {
        if (__comp(__i, __first)) // 特例，不满足__unguarded_linear_insert的前提条件
        {
            typename iterator_traits<_RandomAccessIterator>::value_type
        __val = _GLIBCXX_MOVE(*__i); //move
            _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); //copy_backward
            *__first = _GLIBCXX_MOVE(__val);
        }
        else
        std::__unguarded_linear_insert(__i,
                __gnu_cxx::__ops::__val_comp_iter(__comp));
    }
}

在__insertion_sort 中，如果 __i 比已排序序列中的最小的数 __i 还小，则不满足__unguarded_linear_insert的前提条件。所以需要单独处理，将 __i 插到第一位，后面的元素整体后移一位。

`__final_insertion_sort`

了解了__unguarded_linear_insert的前提条件，__final_insertion_sort 就很好理解了

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

在区间 > 16时，先在[0, 16)上调用了 __insertion_sort；因为[0, 16)中的数可能是完全乱序的，完全不具备调用__unguarded_linear_insert 的前提条件，所以只能用 __insertion_sort。

接着，在[16, end) 处调用了 __unguarded_insertion_sort。由于经过了 __introsort 的数组是整体有序局部乱序的，即 16个一组的子数组内部是乱序的，但是不同子数组之间是有序的，即后一个子数组的最小值一定大于等于前一个子数组的最大值。这意味着[16, end)中的所有数都大于 [0, 16)中的任一个数。于是，[16, end)满足了 __unguarded_insertion_sort 的前提条件。