从零开始的 STL 实现记录：Algorithm-4.5

前言

本节是算法部分的最后一小节了，将会主要介绍 stl_algo.h 中的 sort()，以排序函数作为压轴倒也十分合理，毕竟无论是面试还是工作或学习中的使用，排序都是最经常被提及的一个话题。稍后将会看到，作为对效率有着很高追求的 STL，对于 sort() 函数的设计，依然十分精彩。

sort

STL 所提供的各式各样算法中，sort() 是最复杂最庞大的一个。这个算法接受两个 RandomAccessterators，然后将区间内的所有元素以渐增方式由小到人重新排列.第二个版本则允许用户指定一个仿函数，作为排序标准。STL 中，的所有关系型容器都拥有自动排序功能（底层结构采用 RB-tree，hashtable 不在标准的 STL 范围内），所以不需要用到这个 sort 算法。至于序列式容器中的 stack、queue 和 priority-queue 都有特别的出入口，不允许用户对元素排序。剩下 vector、deque 和 list，前两者的迭代器属于 RandomAccesslterators，适合使用 sort 算法，list 的迭代器则属于 BidirectionelIterators，不适合使用sort算法。

如果要对 list 排序，应该使用它自己提供的 member functions sort()。这一点在介绍 list 的排序算法时也专门强调过，list 的排序。

STL 的 sort 算法，数据量大时采用 Quick Sort、分段递归排序。一旦分段后的数据量小于某个门槛，为避免 Quick Sort 的递归调用带来过大的额外负荷(overhead)，就改用 Insertion Sort。如果递归层次过深，还会改用 Heap Sort（在 heap 中介绍过）。

以下将依次介绍这些排序算法在 STL 中的实现。

insertion Sort

插入排序想必大家都十分清楚，这里就不做介绍了。这个算法的复杂度为O(N^2)，说起来并不理想，但是当数据量很少时，却有不错的效果，原因是实现上有一些技巧（稍后代码可见），而且不像其它较为复杂的排序算法有着诸如递归调用等操作带来的额外负荷。

insertion_sort 也可以接受一个仿函数作为比较元素大小的标准，以下只分析第一个版本。

/// @brief 插入排序函数
template <class RandomAccessIterator>
void insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) return;
    for (auto i = first + 1; i != last; ++i) {
        auto value = *i;
        // 如果 value 比 *first 还小就直接将 value 插在最前的位置，完成对该元素的排序
        if (value < *first) {
            tinystl::copy_backward(first, i, i + 1);
            *first = value;
        }
        // 否则，*first 一定是最小的元素，所以可以直接调用 unchecked_linear_insert，找当前元素的插入位置
        else {
            tinystl::unchecked_linear_insert(i, value);
        }
    }
}

insertion_sort 就是 STL 的插入排序函数了，这个函数不提供给外界使用，一般只作为 sort 算法的一部分使用，虽然上述的函数看似只有一层循环，但无论是 copy_backward 还是 unchecked_linear_insert，都是 O(n) 的复杂度，因此最终的复杂度还是 O(n^2)，在查看 unchecked_linear_insert 函数的实现之前需要了解一下这个前缀 unchecked_x 的含义（STL 中对应的前缀为 unguarded_x）。

上述函数之所以命名为 unguarded_x 是因为，一般的 Insertion Sort 在内循环原本需要做两次判断，判断当前位置该不该插入待排序的元素，同时也判断循环的行进是否超过边界。

但由于上述所示的源代码会导致最小值必然在内循坏子区间的最边缘，所以两个判断可合为一个判断，所以称为 unguarded_。省下一个判断操作，乍见之下无足轻重，但是在大数据量的情况下，影响还是可观的，毕竟这是一个非常根本的算法核心，在大数据量的情况，执行次数非常惊人。

/// @brief 插入排序辅助函数，将 value 插入到 [first, last) 中，不做边界检查
template <class RandomAccessIterator, class T>
void unchecked_linear_insert(RandomAccessIterator last, const T& value) {
    auto next = last;
    --next;
    while (value < *next) {
        *last = *next;
        last = next;
        --next;
    }
    *last = value;
}

查看 unchecked_linear_insert 的实现就会发现，函数内部确实只有一个判断，即 value < *next，此条件为真就一直循环，乍一看确实没有边界检查，可能会死循环。但在 insertion_sort 调用这个函数前，就已经保证了 *first 是最小的元素，因此最后一定会出现 value >= *next 的情况从而跳出循环。

插入排序还有一些其他的函数，这部分得结合 Quick Sort 的过程一起理解，以下就先继续介绍 Qucik Sort。

Intro Sort

Introspective Sort（内省式排序，以下简称 IntroSort） 是 1996 年由 David R. Musser 提出的一种混合式排序法，该算法混合了快速排序与堆排序，使得排序的效率能够维持在 $O(N \log N)$。该算法的基本思想是：先使用 Quick Sort 进行排序，并记录分割的次数，当分割有“恶化”的倾向时（即分割的次数过多），则改用 Heap Sort 进行排序。来看一下这个算法在 STL 中是如何实现的。

/// @brief 内省式排序，先进行 quick sort，当分割行为有恶化倾向时，改用 heap sort
template <class RandomAccessIterator, class Size>
void intro_sort(RandomAccessIterator first, RandomAccessIterator last, Size depth_limit) {
    while (last - first > static_cast<Size>(kThreshold)) {
        // 到达最大分割深度限制，使用 heap_sort
        if (depth_limit == 0) {
            tinystl::partial_sort(first, last, last);
            return;
        }
        --depth_limit;
        // 取三点中值作为 pivot
        auto mid = tinystl::median(*(first), *(first + (last - first) / 2), *(last - 1));
        auto cut = tinystl::unchecked_partition(first, last, mid);
        tinystl::intro_sort(cut, last, depth_limit);  // 对后半段递归
        last = cut;  // 更新 last，持续对前半段进行分割
    }
}

这里的 kThreshold 是一个后面会说明的参数，先按下不表。可以看出，intro_sort 在调用时维护了一个 depth_limit 的参数，并在每次调用都会 --depth_limit，当 depth_limit == 0 说明快排的划分情况已经恶化，此时就会调用 partial_sort，即堆排序；除了 depth_limit == 0 外，其余情况均会重复调用 unchecked_partition，即快排。

此外需要注意的是，这里快排使用的递归似乎与我们平时写的不太一样；通常来说我们是划分完后对数组前半段与后半段分别递归，但这里仅对后半段进行了递归，对于前半段只是不断缩小范围；按照《STL源码剖析》中的说法，这是为了省去递归函数调用时所产生的开销，省去了左半部分的递归，改用循环处理。但这种写法可读性较差，而且效率并不比两次递归更好。

总体思路分析完毕，下面来看看两个排序是如何实现的。

堆排部分的实现

实际上 partial_sort 是对整个区间的前半部分做排序，但在 intro_sort 中都是 partial_sort(first, last, last) 这样调用，因此效果就相当于对整个区间进行堆排序。

/*****************************************************************************************/
// partial_sort
// 对整个序列做部分排序，保证 [first, middle) 内的元素有序且小于 [middle, last) 内的元素
// 思路：
// 1. 在区间 [first, midlle) 上构造大根堆（max-heap）
// 2. 遍历 [middle, last)，如果小于堆顶元素，就将堆顶元素与该元素交换，然后调整堆
// 经过了步骤 2 后可以保证 [first, middle) 内的元素一定小于 [middle, last) 内的元素
// 3. 最后将 [first, middle) 转化为有序序列
/*****************************************************************************************/

/// @brief 对整个序列做部分排序，保证 [first, middle) 内的元素有序且小于 [middle, last) 内的元素
/// 内部使用堆排序
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, 
                  RandomAccessIterator last) {
    tinystl::make_heap(first, middle);
    for (auto i = middle; i != last; ++i) {
        if (*i < *first) tinystl::pop_heap_aux(first, middle, i, *i, distance_type(first));
    }
    tinystl::sort_heap(first, middle);
}

/// @brief 重载版本使用函数对象 comp 代替比较操作
template <class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, 
                  RandomAccessIterator last, Compare comp) {
    tinystl::make_heap(first, middle, comp);
    for (auto i = middle; i != last; ++i) {
        if (comp(*i, *first)) tinystl::pop_heap_aux(first, middle, i, *i, distance_type(first), comp);
    }
    tinystl::sort_heap(first, middle, comp);
}

快排部分的实现

快排部分主要有两个相关的函数，median 与 unchecked_partition。

median 的作用是找到三个数的中间值，再快排中就是用于选择每一次 partition 的“枢纽值”，通过 median(*(first), *(first + (last - first) / 2), *(last - 1)); 的调用方式也不难发现，intro_sort 的每次划分都会选择 first、middle 与 last 三个位置的元素中中间的值作为枢纽值，以避免不合理的划分方式。

/*****************************************************************************************/
// median
// 找出三个值的中间值
/*****************************************************************************************/

/// @brief 找出三个值的中间值，主要用于快排中的 pivot 选择
template <class T>
const T& median(const T& left, const T& mid, const T& right) {
    if (left < mid)
        if (mid < right) return mid;          // left < mid < right
        else if (left < right) return right;  // left < right <= mid
        else return left;                     // right <= left < mid
        
    else if (left < right) return left;     // mid <= left < right
    else if (mid < right) return right;     // mid < right <= left
    else return mid;                        // right <= mid <= left
}

/// @brief 重载版本使用函数对象 comp 代替比较操作
template <class T, class Compared>
const T& median(const T& left, const T& mid, const T& right, Compared comp) {
    if (comp(left, mid))
        if (comp(mid, right)) return mid;
        else if (comp(left, right)) return right;
        else return left;
    else if (comp(left, right)) return left;
    else if (comp(mid, right)) return right;
    else return mid;
}

unchecked_partition 就是实现快排中最重要的“划分”的函数了，负责将 [first, last) 范围内小于 pivot 的元素放到前面，大于 pivot 的元素放到后面，STL 中的实现十分简洁且高效。

令头端迭代器 first 向尾部移动，尾端迭代器 last 向头部移动。当 *first 大于或等于 pivot 时就停下来，当 *last 小于或等于 pivot 时也停下来，然后检验两个迭代器是否交错。如果 first 仍然在左而 last 仍然在石，就将两者元素互换，然后各自调整一个位置（向中央逼近），再继续进行相同的行为。如果发现两个迭代器交错了（亦即 !(first < last) ），表示整个序列已经调整完毕，以此时的 first 为轴，将序列分为左右两半，左半部所有元素值都小于或等于枢轴，右半部所有元素值都大于或等于枢轴。

/// @brief 将 [first, last) 范围内小于 pivot 的元素放到前面，大于 pivot 的元素放到后面
template <class RandomAccessIterator, class T>
RandomAccessIterator unchecked_partition(RandomAccessIterator first, RandomAccessIterator last, 
                                         const T& pivot) {
    while (true) {
        while (*first < pivot) ++first;
        --last;
        while (pivot < *last) --last;
        if (!(first < last)) return first;
        tinystl::iter_swap(first, last);
        ++first;
    }
}

Sort

铺垫了这么多，终于可以介绍最终版本的 sort 了，也是 SGI-STL 中真正使用的排序算法。正如前文所说，STL 的 sort 算法，数据量大时采用 Quick Sort、分段递归排序。一旦分段后的数据量小于某个门槛，为避免 Quick Sort 的递归调用带来过大的额外负荷(overhead)，就改用 Insertion Sort。如果递归层次过深，还会改用 Heap Sort。是一种混合了 Intro Sort 与 Insertion Sort 的排序算法。

至于为什么不直接使用 Intro Sort，《STL源码剖析》中是这样解释的：

面对一个只有十来个元素的小型序列，使用像 Quick Sort这样复杂而（可能）需要大量运算的排序法不划算，在小数据量的情况下，甚至简单如 Insertion Sort 也可能快过 Quick Sort —— 因为 Quick Sort 会为了极小的子序列而产生许多的函数递归调用。
鉴于这种情况,适度评估序列的大小,然后决定采用 Quick Sort 或 Insertion Sort，是值得采纳的一种优化措施。然而究竟多小的序列才应该断然改用insertion Sort呢？并无定论，5~20都可能导致差不多的结果，实际的最佳值因设备而异。
如果我们令某个大小以下的序列滞留在“几近排序但尚未完成”的状态．最后再以一次 Insertion Sort 将所有这些“几近排序但尚未竞全功”的子序列做一次完整的排序，其效率一般认为会比“将所有子序列彻底排序”更好。这是因为 InsertionSort 在面对“几近排序”的序列时，有很好的表现。

STL 中以一个常数定义小型区间的大小，当区间小于这个值时就会转而使用插入排序，也是 intro_sort 中的判断条件，当划分区间长度小于 kThreshold 时便会返回。

constexpr static size_t kThreshold = 16;  // 小型区间的大小，在这个大小内采用插入排序

最终的 sort 函数十分甚至九分的简短，整体逻辑就是先进行 intro_sort，在区间大致有序后再使用 insertion_sort 完成最后的排序。

/// @brief 对 [first, last) 进行排序，先进行 intro_sort，将区间划分为一个个小区间，再对整体使用插入排序
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
        tinystl::intro_sort(first, last, slg2(last - first) * 2);
        tinystl::final_insertion_sort(first, last);
    }
}

其中，slg2 是用与控制分割的最大层次的一个函数，slg2(n) 的作用就是计算 $\lfloor \log_2(n) \rfloor$，即对数的下取整，最终 sort 调用时输入的 depth_limit 为 slg2(last - first) * 2 也就是 $\lfloor 2\log_2(n) \rfloor$，其中 $n$ 为区间长度。当快排的划分层数大于这个值时就转而调用堆排完成剩下的排序。

/// @brief 找出 lgk <= n 的 k 的最大值，用于控制分割恶化的情况
template <class Size>
Size slg2(Size n) {
    Size k;
    for (k = 0; n > 1; n >>= 1) ++k;
    return k;
}

最后要提的是 final_insertion_sort，该函数会根据区间长度来实现插入排序，若区间长度小于 kThreshold，就直接调用 insertion_sort，否则会在前一个区间上调用 insertion_sort，后半段直接调用 unchecked_insertion_sort，可以节省边界条件判断。

/// @brief 插入排序函数，不做边界检查
template <class RandomAccessIterator>
void unchecked_insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    // 从 first + 1 开始排序
    for (auto i = first; i != last; ++i) {
        tinystl::unchecked_linear_insert(i, *i);
    }
}

/// @brief 插入排序函数
template <class RandomAccessIterator>
void final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    // 如果排序区间长度大于 kThreshold，就对分别对前后两个区间进行插入排序
    // 之所以分成两个区间是因为要保证最小元素在数组边缘，这样才能减少一个判断
    if (last - first > static_cast<ptrdiff_t>(kThreshold)) {
        // 由于 intro_sort 以 kThreshold 为界限，因此最小元素一定在前 kThreshold 个元素中
        tinystl::insertion_sort(first, first + static_cast<ptrdiff_t>(kThreshold));
        tinystl::unchecked_insertion_sort(first + static_cast<ptrdiff_t>(kThreshold), last);
    }
    else {
        tinystl::insertion_sort(first, last);
    }
}

这就是 STL 中排序算法的全貌了，想必一定没有让你失望，对于 sort 的各种优化也是 STL 算法中设计最精妙与复杂的。

nth_element

此外还要介绍一个算法：nth_element，这个算法也很巧妙并且与 sort 的关联性很强，因此一并分析了。

nth_element(first, nth, last) 的功能为对区间进行重排，使得执行完后的第 nth 个元素刚好在排完序后的位置上。换言之，执行完后的区间看起来就像是以第 nth 个元素为 pivot 做了一次 partition，比第 nth 个元素小的元素全在它之前，比它大的元素则在其之后，但前后区间内部不保证有序。

如序列 {1 5 4 3 2}，执行 nth_element(v.begin(), v.first + 2, v.end()) 后会变成 {2 1 3 4 5 }，排序的话就会发现 v.begin() + 2 确实在它排序后应该在的位置，但前后区间并不是完全有序的。

TinySTL 中该函数的实现如下。

STL 中这个函数的实现甚至也使用了和 sort 一样的手法，会设置一个阈值，划分恶化会选择基于堆的另一种选择算法 heap_select，简直丧心病狂，有兴趣的读者可以自行查看源码，这里就不实现这么复杂的功能了。

/*****************************************************************************************/
// nth_element
// 对序列重排，使得所有小于第 n 个元素的元素出现在它的前面，大于它的出现在它的后面
// 思路：
// 1. 选取三点中值作为 pivot，对序列进行分割
// 2. 若 nth 元素落在分割点左侧，对左侧序列递归调用 partition，否则对右侧序列递归调用 partition
// 3. 重复上述过程，直到分割区间长度小于等于 3，然后对这个区间进行插入排序
/*****************************************************************************************/

/// @brief 对序列重排，使得所有小于第 n 个元素的元素出现在它的前面，大于它的出现在它的后面
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) {
    if (nth == last) return;
    while (last - first > 3) {
        // 选取三点中值作为 pivot 进行分割
        auto cut = tinystl::unchecked_partition(first, last, 
            tinystl::median(*first, *(first + (last - first) / 2), *(last - 1)));
        // nth 元素落在分割点右侧，对右侧序列继续调用 partition
        if (cut <= nth) first = cut;
        // nth 元素落在分割点左侧，对左侧序列继续调用 partition
        else last = cut;
    }
    // 对分割区间进行插入排序
    tinystl::insertion_sort(first, last);
}

/// @brief 重载版本使用函数对象 comp 代替比较操作
template <class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, 
                 RandomAccessIterator last, Compare comp) {
    if (nth == last) return;
    while (last - first > 3) {
        // 选取三点中值作为 pivot 进行分割
        auto cut = tinystl::unchecked_partition(first, last, 
            tinystl::median(*first, *(first + (last - first) / 2), *(last - 1), comp), comp);
        // nth 元素落在分割点右侧，对右侧序列继续调用 partition
        if (cut <= nth) first = cut;
        // nth 元素落在分割点左侧，对左侧序列继续调用 partition
        else last = cut;
    }
    // 对分割区间进行插入排序
    tinystl::insertion_sort(first, last, comp);
}

总体来说就是不断调用以三点中值作为 pivot 的 unchecked_partition，因为每一次 partition 都能确保 cut 处的元素会位于排序后相同的位置，但 cut 的位置不一定是我们想要的 nth，因此就根据 cut 的位置持续调用 partition 就能达到目的；具体而言，如果 nth 在 cut 的左侧，就在左侧区间持续调用 partition，否则在右侧区间调用，直至处理的区间长度小于等于3，此时直接使用插入排序即可完成任务。

总结

本节主要分析了 sort 的精彩实现以及 nth_element 的实现。至此，STL 中的算法部分就分析完毕了。

通过这几节的分析可以看出，STL 中的算法都不仅仅是实现功能这么简单，还针对各种情况做了许多优化，这才使得 STL 的算法效率如此之高，这其中许多算法的设计与思想都很值得我们学习，例如 copy()、sort() 等。

当然，博主分析的只是 STL 算法的一小部分内容，TinySTL 中实现的算法要更多，并且 STL 库中还有许多其他有趣的算法，剩下的就留给感兴趣的读者自行探索了。

下一节将开始分析 STL 六大组件之五的 Functor。