STL算法之sort

STL所提供的各式各样算法中，sort()是最复杂最庞大的一个。这个算法接受两个RandomAccessIterators(随机存取迭代器)，然后将区间内的所有元素以渐增方式由小到大重新排列。还有一个版本则是允许用户指定一个仿函数代替operator<作为排序标准。STL的所有关联式容器(associative containers)都拥有自动排序功能(底层结构为RB-tree，见STL关联式容器介绍_stl 关联式容器-CSDN博客)，所以不需要用到这个sort算法。至于序列式容器(sequence containers)中的stack，queue和priority-queue都有特别的入口，不允许用户对元素排序。剩下vector、dequeue和list，前两者的迭代器属于RandomAccessIterators，适合使用sort算法，list的迭代器则属于BidirectionalIterators,都不适合使用sort算法。如果要对list或slist排序，应该使用它们自己提供的成员函数sort()。稍后我们便可以看到为什么泛型算法sort()一定要求RandomAccessIterators。

排序有多么重要

人类生活在一个有序的世界中。没有排序，很多事情无法进行。排过序的数据，特别容易查找。电话簿总是以人名为键值来排序，对人名而言，电话簿是有序的，对电话号码而言，电话簿是无序的。在电话簿里找一个人(从而得到他的电话号码)很容易，但我们能想象再电话簿里头不通过人名查找某个特定的电话号码吗？

这类情况大量发生在日常生活中。字典需要排序，书籍索引需要排序，磁盘目录需要排序，名片需要排序，图书馆藏需要排序，户籍数据需要排序。任何数据只要你想快速查找，具需要排序。

犹有进者，排序可能使其他工作更快更轻松。如果你要确定(或找出)一堆数据里头没有有重复的元素，先排序一遍再找，会比闷着头两两比对快快得多。换句话说，许多算法可能因为数据先行排序过而大幅改善效率。排序的成本，成为影响执行时间的关键因素。

STL算法的sort算法，数据量大时采用Quik Sort，分段递归排序。一旦分段后的数据量小于某个门槛，为了避免Quik Sort的递归调用带来过多额外负担(overhead)，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort参见STL序列式容器之heap（堆）_stl 堆-CSDN博客。以下分别介绍Quick Sort和Insertion Sort，然后再整合起来介绍STL sort算法。

Insertion Sort

Insertion Sort以双层循环的形式进行。外循环遍历整个序列，每次迭代决定出一个子区间；内循环遍历子区间，将子区间内的每一个“逆转对(inversion)”倒转过来。所谓“逆转对”是指任何两个迭代器i、j，i<j,而*i>*j。一旦不存在逆转对，序列即排序完毕。这个算法的时间复杂度为 $O(N^2)$ ，说起来并不理想，但是当数据量很少时，却有不错的效果，原因是实现上有一些技巧(稍后源代码可见)，而且不像其它比较复杂的排序算法有着诸如递归调用等操作带来的额外负担。下图是Insertion Sort的详细步骤示意：

图中左下部分的三角形内部，每一行都是有序的序列；每次往有序序列中增加一个元素，依次采用插入到正好使序列依然保持有序状态的方式进行；固而得名插入排序(Insertion Sort)。

SGI STL的Insert Sort有两个不同的版本，一个使用默认的operator<,另个使用仿函数comp代替。以下列出版本一。由于STL规格并不开放Insert Sort，所以SGI将以下函数的名称都加上了双下划线，表示内部使用。

//版本一
template <class RandomAccessIterator>
void __intertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) return ;
    for (RandomAccessIterator I = first + 1, I != last; ++I) 
        __linear_insert(first, I, value_type(first));
}

template <class RandomAccessIterator, class T>
void __linear_insert(RandomAccessIterator  first, RandomAccessIterator last, T*) {
    T value = *last;
    if (value < *first) {
        copy_backward(first, last, last+1); // 当前最后一个元素比原有序序列，最小元素还小
        *first = value;                     // 将原序列，往后移一个位置，将新的最小元素放置到最前面
    } else
        __unguarded_linear_inserrt(last, value);
    
}


template <class RandomAccessIterator, class T>
void __unguarded_linear_inserrt(RandomAccessIterator last, T value) {
    RandomAccessIterator next = last;
    --next;
    while(value < *next) { // 新加入的元素比当前元素小，
        *last = *next;     // 则将当前元素往后挪，否则就再该位置填入新加入的值
        last = next;
        --next;
    }
    *last = value;
}

上述函数之所以命名为unguarded_x是因为，一般的Insert Sort在内循环原本需要做两次判断，判断是否相邻两元素使“逆转对”，同时也判断循环是否超过边界。但由于上述所示的代码会导致最小值必然在内循环子区间的最边缘，所以两个判断可合为一个判断，所以成为unguarded_。省下一个判断操作，乍见之下无足轻重，但是在大数据量的情况下，影响还是可观的，毕竟这是一个非常根本的算法核心，在大数据量的情况下（大量调用？），提效会非常惊人。

稍后出场的几个函数，也有以unguarded_为前缀命名者，同样是在特定情况下，边界条件的检验可以省略(或说已融入特定条件之内)。

Quick Sort

如果我们拿Insertion Sort来处理大量数据，其 $O(N^2)$ 的复杂度就令人摇头了。大数据量的情况下有许多更好的排序可供选择。正如其名称所昭示，Quik Sort是目前已知最快的排序法，平均复杂度为 $O(N LogN)$ ,最坏情况下将达到 $O(N^2)$ 。不过IntroSort(极类似 median-of-three QuickSort的一种排序算法)可将最坏情况推进到 $O(N LogN)$ 。早期的STL sort算法都采用Quick Sort，SGI STl已改用IntroSort。

Quick Sort算法可以叙述如下。假设S代表将被排序的序列：

如果S的元素个数为0或1，结束。
取S中的任何一个元素，当做枢轴(pivot)v。
将S分割为L，R两段，使L内的每一个元素都小于或等于v，R内的每一个元素大于或等于v。
对L，R递归执行Quick Sort

Quick Sort的精神在于将大区间分割为小区间，分段排序。每一个小区间排序完成后，串接起来的大区间也就完成了排序。最坏的情况下发生在分割(partition)时产生出一个空的子区间--那完全没有达到分割的预期效果。下图说明了Quick Sort的分段排序过程

Median-of-Three(三点中值)

注意任何一个元素度可以被选来当做枢轴(pivot)，但是其合适与否却影响Quick Sort的效率，为了避免“元素当初输入时不够随机”所带来的恶化效应，最理想最稳当的方式就是取整个序列的头、尾、中央三个位置的元素，以其中值(median)作为枢轴。这种做法称为median-of-three partition，或称为mediun-of-three-QuickSort。为了能够快速取出中央位置的元素，显然随机迭代器必须能随机定位，亦即必须是个RandomAccessIterators。

以下是SGI STL提供的三点中值决定函数：

template<class T>
inline const T& __median(const T& a, const T& b, const T& c) {
    if (a < b) 
        if (b < c) // a < b < c
            return b;
        else if (a < c) 
            return c; // a  < b, b >= c, a < c
        else 
            return a;
    else if (a < c)    // c> a>= b
        return a;
    else if (b < c)    // a >= b, a>=c, b <c
        return c;
    else 
        return b;
}

Partition(分割)

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

下面SGI STL提供的分割函数，其返回值是分割后的有段第一个位置：

template<class RandomAcccessIterator, class T>
RandomAcccessIterator __unguarded_partion(RandomAcccessIterator first,
                                          RandomAcccessIterator last,
                                          T pivot) {
    while(true) {
        while(*first < pivot) ++first;
        --last;
        while(pivot < *last) --last;
        if (!(first < last)) return first;
        iter_swap(first, last);
        ++first;
    }
}

下图是分割实例的完整过程：

threshold(阈值)

面对一个只有十来个元素的小型序列，使用Quick Sort这样复杂而（可能）需要大量运算的排序法，是否划算?不，不划算，在小数据量的情况下，甚至简单如Insert Sort者也可能快过Quick Sort--因为Quick Sort会为了极小的子序列产生许多的函数递归调用。

鉴于这种情况，适度评估序列的大小，然后决定采用Quick Sort或Insertion Sort，是值得采纳的一种优化措施。然后究竟多小的序列才应该断然改用Insertion Sort？并无定论，5~20都可能导致差不多的结果，实际的最佳值因设备而异。

final insertion sort

优化措施用不嫌多，只要我们不是贸然行事。如果我们令某个大小以下的序列滞留在"几近排序但尚未竟全功"的子序列做一次完整的排序，其效率一般认为会比“将所有子序列彻底排序”更好。这是以为Insertion Sort在面对“几近排序”的序列时，有很好的表现。

introsort

不当的枢轴选择，导致不当的分割。导致Quick Sort恶化未 $O(N^2)$ .David R. Musser于1996年提出易总混合式排序算法：Introspective Sorting（内省式排序），简称Intro Sort，其行为在大部分情况下几乎与median-of-3 Quick Sort 完全相同(当然也一样快)。但是当分割行为有恶化未二次行为的倾向时，能够自我侦测，转而改用Heap Sort，使效率维持在Heap Sort的 $O(N logN)$ ,又比一开始就使用Heap Sort来得好。稍后边可以看到SGI STL源代码中对IntroSort的实现。

SGI STL sort

下面是SGI STL sort()源代码

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
        __introsort_loop(first, last, value_type(first), __lg(last-first)*2);
        __final_insertion_sort(first, last);
    }   
}

其中__lg()用来控制分割恶化的情况

// 找出2^k <= n 的最大值k,例：n=7,得k=2；n=20的k=4；n=8，得k=3
template <class Size>
inline Size __lg(Size n) {
    Size k;
    for (k = 0; n>1; n >>= 1) ++k;
    return k;
}

__introsort_loop() 最后一个参数表示递归的最深层次不应超过2*log(N),代码如下：

template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last, T*, Size depth_limit) {
    while ((last - first) > __stl_threshold) { // __stl_threashold = 16,全局常量
        if (depth_limit == 0) {
            partial_sort(first, last, last); // 改用heapsort
        }   
        --depth_limit;
        RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first,
                                                                                *(first + (last - first)/2),
                                                                                *(last-1))));
        // 右半段递归进行sort
        __introsort_loop(cut, last, value_type(first), depth_limit);
        last = cut;
        // 因为重置了last，所以左半段继续进行排序
    }   
}

函数一开始判断序列的大小.__stl_threshold是个全局整型常数，定义如下

const int __stl_threshold = 16;

通过元素个数检验后，再检查分割层次。如果分割层次超过指定值，就改用partital_sort(), 事实上调用的是Heap Sort。

都通过了这些检验之后，便进入Quik Sort完全相同的程序：以median-of-3方法确定枢轴位置，然后调用__unguarded_partition()找出分割点，然后针对左右段递归进行IntroSort。

当__introsort_loop()结束，[first, last)内有多个“元素个数少于16”的子序列，每个子序列都有相当程度的排序，但尚未排序(以为元素个数一旦小于__stl_threshold，就被中止进一步的排序操作了)。回到母函数sort()，再进入__final_insertion_sort():

template <RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (last - first > __stl_threshold) { // 16
        __insertion_sort(first, first + __stl_threshold);
        __unguarded_insertion_sort(first + __stl_threshold, last);
    } else {
        __insertion_sort(first, last);
    }
}

此函数首先判断元素个数是否大于16.如果答案为否，就调用__insertion_sort()加以处理。如果答案为是，就将[first, last)分割为长度为16的一段子序列，和另一段剩余子序列，再针对两个子序列分别调用__insert_sort()和__unguarded_insertion_sort().前者代码已于先前展示，后者源代码如下：

template <RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    __unguarded_insertion_sort_aux(first, last, value_type(first));
}

template <RandomAccessIterator>
void __unguarded_insertion_sort_aux(RandomAccessIterator first, RandomAccessIterator last, T*) {
    for (RandomAccessIterator i = first, i != last; ++i)  
        __unguarded_linear_insert(i, T(*i));
}

这就是SGI STL sort算法的完整过程。为了做个比较，我们再列出RW STL sort的部分源代码，RW版本用的是纯粹Quick Sort，不是Intro Sort

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (!(first == last)) {
        __quick_sort_loop(first, last);
            __final_insertion_sort(first, last); //其内兼容于SGI STL完全相同
    }
}

template <class RandomAccessIterator>
inline void __quick_sort_loop(RandomAccessIterator first, RandomAccessIterator last) {
    __quick_sort_loop_aux(first, last, _RWSTD_VALUE_TYPE(first));
}

template <class RandomAccessIterator, class T>
inline void __quick_sort_loop_aux(RandomAccessIterator first, RandomAccessIterator last, T*) {
    while (last - first > __stl_threshold) {
        // median-of-3 partitioning
        RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first)/2), *(last - 1))));

        if (cut - first > last - cut) {
            __quick_sort_loop(cut, last);    // 较短段以递归方式处理
            last = cut;
        } else {
            __quick_sort_loop(first, cut);    // 较短段以递归方式处理
            first = cut;

        }
    }
}

参考文档《STL源码剖析--侯捷》