STL sort 源码解析

前言

——本文整理自《STL源码解析》
虽然源码解析的代码比较老但是核心思想并没有太多变化并且直接看源码有太多细节我又看不懂最新的。

简介

sort接受两个RandomAccessIterators(随机存储迭代器)，然后将区间内的所有元素以渐増的方式由小到大重新排列，第二个版本允许用户指定一个仿函数作为排序标准，STL所有关系型容器都拥有自动排序功能，不需要sort,stack,queue,priority-queue都有特别出入口，不允许排序，剩下vector，deque和list,前两者的迭代器属于RandomAccessIterators，适合sort，而list的迭代器属于BidirectionalIterators。

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

Insertion Sort

template <class RandomAccessIterator>
void __insertion_sort (RandomAccessIterator first,
                        RandomAccessIterator last){
   if(first == last) return;
   for(RandomAccessIterator i= first + 1; i != last; ++i){
      __linear_insert(first,i,value_type(first));
      //[first,i)形成一个子区间
   }
}
//版本一辅助函数
template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first,
                            RandomAccessIterator last, T*){
   T value  = *last;//记录末尾元素
   if(value < *first){ //如果尾部的值比头还小（头端必为最小元素）
      //无须比较 直接平移
      copy_backward(first, last, last + 1);
      *fist = value;
   }  
   else //尾部不小于头部
    __unguarded_linear_insert(last,value);                        
}

//版本一辅助函数
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value){
   RandomAccessIterator next = last;
   --next;
   //insertion sort 的内循环
   //一旦不出现逆序对循环即可结束
   while(value < *next){ //逆序对存在
      *last = *next;     //调整
      last = next;      //调整迭代器
      --next;//左移一个位置
   }
   *last = value; //把value的值移动到正确的
}

上述函数之所以被命名为unguarded_x是因为，一般的Insertion Sort在内层循环需要做两次判断，判断两相邻元素是否是“逆序对”
同时也判断是否出界，然而现在保证最小值必然在内层子区间的最边缘，所以合成为一次判断，这在数据量很大的时候，执行次数相当惊人。

之后以unguarded_x命名原因相似。

Median-of-Three(三点中值)

//返回 a,b,c之居中者
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) // a < b, b >= c, a < c
            return 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;
    return b;
}

Partitioning (分割)

SGI STL 提供的分割函数，其返回值为分割后的右端第一个位置:

//版本一 
template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
    RandomAccessIterator last,
    T pivot) {
    while (true) {
        --last;
        while (*first < *last) ++first; //first 找到 >= pivot的元素就停下来
        --last;  //调整
        while (pivot < *last) --last; //last找到 <= pivot 的元素就停下来
        //一下first<last 判断操作只适用于 random iterator
        if (!(first < last)) return first; //交错，结束循环
            iter_swap(fist, last);//大小值交换
        ++first;//调整
    }
}

threshold (阈值)

面对一个只有几十个元素的小型序列，使用Quick Sort这样复杂而可能需要大量运算的排序法不划算，因为在小数据量的情况下，甚至简单的Insertion Sort 也可能快过Quick Sort——因为Quick Sort会为了极小的子序列而产生许多的函数递归调用。
所以需要适当评估并优化算法。

final insertion sort

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

introsort

不当枢轴选择会导致不当的分割，导致Quick Sort迅速恶化。David R. Musser 于1996年提出一种混合式排序算法Introspective Sorting,(内省式排序)简称InstroSort其行为在大部分情况下和上述相同，但是当分割行为有而化为二次行为的倾向时，能自我侦测，从而改用Heap Sort，使其效率维持在Heap Sort的O(NlogN)。

//版本一
//千万注意：sort()只适用于RandomAccessIterator
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;
}

    //当元素个数为40时，__introsort_loop()的最后一个参数将是5*2，意思是最多允许分割10层。

IntroSort算法如下：

//版本一
//注意，本函数内的许多迭代器运算操作，都只适用于RandomAccess Iterators
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
    RandomAccessIterator last, T*,
    Size depth_limit) {
    //以下， __stl_threshold 是个全局阐述，稍早定义为 const int 16
    while (last - first >= __stl_threshold) { // > 16
        if (depth_limit == 0) {             //至此，分裂恶化
            partial_sort(first, last, last);//改用heapsort
            return;
        }
        --depth_limit;
        //以下分别是 median-of-3 partition，选择一个够好的枢轴并决定分割点
        //分割点将落在迭代器cut 身上
        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;
        //现在回到while循环，准备对左半段递归进行sort
        //这种写法可读性差，效率并没有比较好
        // RW STL ， 采用一般教科书写法（直观地对左半段和右半段递归），较易阅读
    }
}

函数一开始就判断序列大小，__stl_threshold是个全局整数型产生u，定义如下：
const int __stl_threshold = 16 ;
通过元素个数检查之后，再检查分割层次，如果分割层次超过指定值（我已在前一段文字中对此作了说明），就改用partial _sort(),psrtial_sort()是以Heap Sort完成的。

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

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

//版本一
template <class 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);
    }
    __insertion_sort(first, last);
}

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

//版本一
template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
    RandomAccessIterator last) {
    __unguarded_insertion_sort_aux(first, last, value_type(first));
}
//版本一
template <class RandomAccessIterator,class T>
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不是IntroSort。

RW STL sort()

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first,
    RandomAccessIterator last)
{
    if (!(first == last))
    {
        __quick_sort_loop(first, last);
        __final_insertion_sort(first, last);
    }
}

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

template <class RandomAccessIterator,class T>
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_soort_loop(cut, last);//对右段递归处理
            last = cut;
        }
        else
        {
            __quick_sort_loop(first,cut);
            first = cut;
        }
    }
}