前言
-- 本文整理自《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;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3394649.html