6.7.9 sort

      STL的所有关系型容器（set,map,multiset……）都拥有自动排序功能（底层结构采用RB-tree），不需要sort算法。序列式容器stack、queue和priority-queue不允许排序。剩下的vector、deque和list，前两个适合使用sort排序，list迭代器不属于随机存取迭代器，不适合使用sort排序。

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

Insertion Sort

      插入排序算法，__insertion_sort以双层循环形式进行。外循环遍历整个序列，每次迭代决定出一个子区间；内循环遍历子区间，将子区间内的每一个“逆转对”倒转过来，如果一旦不存在“逆转对”，表示排序完毕。

“逆转对”概念：指任何两个迭代器i和j，i<j,而*i>*j.

 

// sort() and its auxiliary functions.
//__insertion_sort版本一的辅助函数
template <class _RandomAccessIter, class_Tp>
void__unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {_RandomAccessIter __next = __last;--__next;//__insertion_sort的内循环//注意：一旦不再出现逆转对，循环就结束while (__val < *__next) {//存在逆转对*__last = *__next;//调整元素__last = __next;//调整迭代器--__next;//左移一个位置}*__last = __val;//value的正确插入位置
}
//__insertion_sort版本二的辅助函数
template <class _RandomAccessIter, class_Tp, class _Compare>
void__unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,_Compare __comp){_RandomAccessIter __next = __last;--__next; while (__comp(__val, *__next)) {*__last = *__next;__last = __next;--__next;}*__last = __val;
}
//__insertion_sort版本一的辅助函数
template <class _RandomAccessIter, class_Tp>
inline void__linear_insert(_RandomAccessIter __first,_RandomAccessIter__last, _Tp*) {_Tp__val = *__last;//记录尾元素if(__val < *__first) {//尾元素比头元素还小//将整个区间向右移一个位置copy_backward(__first, __last, __last + 1);*__first = __val;//令头元素等于原先的尾元素//以上两行命令的功能相等于交换两个元素}else//尾元素不小于头元素__unguarded_linear_insert(__last, __val);
}
//__insertion_sort版本二的辅助函数
template <class _RandomAccessIter, class_Tp, class _Compare>
inline void__linear_insert(_RandomAccessIter __first,_RandomAccessIter__last, _Tp*, _Compare __comp) {_Tp__val = *__last;if(__comp(__val, *__first)) {copy_backward(__first, __last, __last + 1);*__first = __val;}else__unguarded_linear_insert(__last, __val, __comp);
}
//__insertion_sort以双层循环形式进行。外循环遍历整个序列，每次迭代决定出一个子区间；
//内循环遍历子区间，将子区间内的每一个“逆转对”倒转过来，如果一旦不存在“逆转对”，表示排序完毕。
//“逆转对”概念：指任何两个迭代器i和j，i<j,而*i>*j.
//版本一
template <class _RandomAccessIter>
void __insertion_sort(_RandomAccessIter__first, _RandomAccessIter __last) {if(__first == __last) return; //若区间为空，则退出for(_RandomAccessIter __i = __first + 1; __i != __last; ++__i)//外循环，遍历整个区间//[first,i)形成的子空间__linear_insert(__first, __i, __VALUE_TYPE(__first));
}
//版本二
template <class _RandomAccessIter, class_Compare>
void __insertion_sort(_RandomAccessIter__first,_RandomAccessIter __last,_Compare __comp) {if(__first == __last) return;for(_RandomAccessIter __i = __first + 1; __i != __last; ++__i)//外循环__linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);//[first,i）形成一个子区间
}

插入排序算法如下图所示：

Quick Sort

      快速排序算法是目前已知最快的排序法，平均复杂度为O(NlogN)，最坏情况下将达O(N^2)。不过下面介绍的IntroSort可将最坏情况推进到O(NlogN)。SGI STL以改用IntroSort排序。

快速排序的过程如下：

1、  如果S的元素个数为0或1，结束。

2、  取S中的任何一个元素，当作枢轴（pivot）v。

3、  将S分割为L、R两段，使L内的每一个元素都小于或等于v，R内的每一个元素都大于或等于v。这样枢轴v的位置就确定了。

4、  对L、R递归执行QuickSort。

Median-of-Three（三点中值）

任何元素都可以被选来作为枢轴，但为了避免“元素当初输入时不够随机”所带来的恶化效应，最理想的方式是取整个序列的头、尾、中央三个位置的元素，以其中值作为枢轴。这种做法称为Median-of-Three patitioning。

// __median (an extension, not present in the C++ standard).  
//函数功能：取三个元素a，b，c的中间值  
//版本一采用默认的operator<操作  
template <class _Tp>  
inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {  __STL_REQUIRES(_Tp, _LessThanComparable);  if (__a < __b)  if (__b < __c)  return __b;//若a<b<c，则返回b  else if (__a < __c)  return __c;//若a<c<b，则返回c  else  return __a;//若c<a<b，则返回a  else if (__a < __c)  return __a;//若b<a<c，则返回a  else if (__b < __c)  return __c;//若b<c<a，则返回c  else  return __b;//否则返回b  
}  
//版本二采用仿函数comp比较  
template <class _Tp, class _Compare>  
inline const _Tp&  
__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {  __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);  if (__comp(__a, __b))  if (__comp(__b, __c))  return __b;  else if (__comp(__a, __c))  return __c;  else  return __a;  else if (__comp(__a, __c))  return __a;  else if (__comp(__b, __c))  return __c;  else  return __b;  
}  

Partitioning（分割）

//找出快速排序的枢纽位置
//版本一采用operator<
template <class _RandomAccessIter, class_Tp>
_RandomAccessIter__unguarded_partition(_RandomAccessIter __first,_RandomAccessIter __last,_Tp__pivot)
{//找出枢纽轴的位置//令头端迭代器向尾端方向移动，尾端迭代器向头端移动。//当*first不小于枢纽值时，就停下来，当*last不大于枢纽值时也停下来，然后检测两个迭代器是否交错//如果first仍然在左侧而last仍然在右侧，就交换两个元素，然后各自调整位置，向中央逼近，再继续执行相同的行为.//直到first和last两个迭代器交错，此时表示已找到枢纽轴位置即first所在的位置while (true) {while (*__first < __pivot)++__first;//first向尾端移动，直到遇到不小于枢纽值时，停止--__last;while(__pivot < *__last)--__last;//last向头端移动，直到遇到不大于枢纽值时，停止if (!(__first < __last))//检测两个迭代器是否交错return __first;//交错，则此时已找到，即为first迭代器所指位置iter_swap(__first, __last);//否则交换迭代器所指的元素++__first;//继续执行相同行为}
}   

分割的过程如下：

//版本一采用__comp
template <class _RandomAccessIter, class_Tp, class _Compare>
_RandomAccessIter__unguarded_partition(_RandomAccessIter __first,_RandomAccessIter __last,_Tp__pivot, _Compare __comp)
{while (true) {while (__comp(*__first, __pivot))++__first;--__last;while (__comp(__pivot, *__last))--__last;if (!(__first < __last))return __first;iter_swap(__first, __last);++__first;}
}const int __stl_threshold = 16;//阈值//sort版本一的辅助函数
template <class _RandomAccessIter>
inline void__unguarded_insertion_sort(_RandomAccessIter __first,_RandomAccessIter __last) {__unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
}template <class _RandomAccessIter, class_Tp, class _Compare>
void__unguarded_insertion_sort_aux(_RandomAccessIter __first,_RandomAccessIter __last,_Tp*,_Compare __comp) {for(_RandomAccessIter __i = __first; __i != __last; ++__i)__unguarded_linear_insert(__i, _Tp(*__i), __comp);
}template <class _RandomAccessIter, class_Compare>
inline void__unguarded_insertion_sort(_RandomAccessIter __first,_RandomAccessIter __last,_Compare__comp) {__unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first),__comp);
}
//sort版本一的辅助函数
template <class _RandomAccessIter>
void__final_insertion_sort(_RandomAccessIter __first,_RandomAccessIter__last) {if(__last - __first > __stl_threshold) {//判断元素个数是否大于16//则把区间分割成两段，一端长度为16，另一端为剩余的长度__insertion_sort(__first, __first + __stl_threshold);__unguarded_insertion_sort(__first + __stl_threshold, __last);}else//若不大于16，直接调用插入排序__insertion_sort(__first, __last);
}template <class _RandomAccessIter, class_Compare>
void__final_insertion_sort(_RandomAccessIter __first,_RandomAccessIter__last, _Compare __comp) {if(__last - __first > __stl_threshold) {__insertion_sort(__first, __first + __stl_threshold, __comp);__unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);}else__insertion_sort(__first, __last, __comp);
}
//_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

      内省式排序，混合式排序算法，其行为在大部分情况下几乎与快速排序相同，但是当分割行为有恶化为二次行为的倾向时，能够自我侦测，转而改用Heap Sort（堆排序），使效率维持在堆排序的O(NlogN)。

//sort版本一的辅助函数
//参数__depth_limit表示最大的分割层数
template <class _RandomAccessIter, class_Tp, class _Size>
void __introsort_loop(_RandomAccessIter__first,_RandomAccessIter __last,_Tp*,_Size __depth_limit)
{//__stl_threshold为全局常量，其值为16while (__last - __first > __stl_threshold) {//若区间长度大于16if (__depth_limit == 0) {//表示分割恶化partial_sort(__first, __last, __last);//转而调用堆排序heap_sort()return;}--__depth_limit;//计算分割点cut，枢纽值是采用首、尾、中央三个的中间值_RandomAccessIter __cut =__unguarded_partition(__first, __last,_Tp(__median(*__first,*(__first + (__last - __first)/2),*(__last - 1))));//对右半部分递归地进行排序__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);__last = __cut;//接下来对左半部分递归地进行排序}
}template <class _RandomAccessIter, class_Tp, class _Size, class _Compare>
void __introsort_loop(_RandomAccessIter__first,_RandomAccessIter __last,_Tp*,_Size __depth_limit,_Compare __comp)
{while (__last - __first > __stl_threshold) {if (__depth_limit == 0) {partial_sort(__first, __last, __last, __comp);return;}--__depth_limit;_RandomAccessIter __cut =__unguarded_partition(__first, __last,_Tp(__median(*__first,*(__first + (__last - __first)/2),*(__last - 1), __comp)),__comp);__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);__last = __cut;}
}
//SGI STL的排序算法，迭代器参数的类型必须是随机访问迭代器_RandomAccessIter
/*
函数功能：Sorts the elements in the range [first,last) into ascending order.
函数原型：
default (1)         ：版本一采用默认的operator<template<class RandomAccessIterator>voidsort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)        ：版本二采用仿函数comptemplate<class RandomAccessIterator, class Compare>voidsort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);*/
//版本一
template <class _RandomAccessIter>
inline void sort(_RandomAccessIter __first,_RandomAccessIter __last) {__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);__STL_REQUIRES(typenameiterator_traits<_RandomAccessIter>::value_type,_LessThanComparable);//_lg()函数是用来控制分割恶化的情况if(__first != __last) {__introsort_loop(__first, __last,__VALUE_TYPE(__first),__lg(__last - __first) *2);//进行插入排序__final_insertion_sort(__first, __last);}
}
//版本二
template <class _RandomAccessIter, class_Compare>
inline void sort(_RandomAccessIter __first,_RandomAccessIter __last,_Compare __comp) {__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);__STL_BINARY_FUNCTION_CHECK(_Compare, bool,typename iterator_traits<_RandomAccessIter>::value_type,typename iterator_traits<_RandomAccessIter>::value_type);if(__first != __last) {__introsort_loop(__first, __last,__VALUE_TYPE(__first),__lg(__last - __first) *2,__comp);__final_insertion_sort(__first, __last, __comp);}
}