本文共 3537 字，大约阅读时间需要 11 分钟。
Sort函数比较复杂，底层用到了改进快速排序（用3点中值法，确定枢轴），堆排序，插入排序。
总体来说，sort是以快速排序算法为基础进行优化的，优化主要体现在3个方面：
1、任何元素都可以被当做枢轴，但是其合适与否却会影响效率。为了避免元素初始不够随机所带来的恶化效应，取整个队列首、尾、中央三个位置的元素，以其中值作为枢轴。
2、不当的枢轴选择会导致快速排序的效率恶化为O(N2)，此种现象的表现是递归深度过深，用序列长度的函数限制递归深度（2*lgN），当超过该值时，采用堆排序。
这里对2*lgN稍微解释下，其实快速排序的递归表现为对序列的切分，最终的效果是切割成为长度为1的区间，最理想的效果是每次都折半切分，那么递归深度为lgN；最差的情况，递归深度为N；实际上由于输入序列的随机性，深度在lgN~N之间，2*lgN是人为设置的一个界限。
这个思路也可以用来分析大部分具有NlgN复杂度的排序算法的复杂度。对每个元素，都存在lgN的递归代价，那么N个元素复杂度为N*lgN。注意这是最理想的，实际上会存在一个大于1的系数。堆排序、归并排序、快速排序、以及他们的改进排序算法复杂度均为O（NlgN），他们的区别就体现在系数的大小，一般快速排序的系数最小，效果最好。
3、对于小型序列（10个元素左右，STL阈值设置为16），简单的插入排序效果会好于快速排序，因此在快速排序的切分过程中，当子序列小于16时，切换成插入排序。STL采用的方式并不是立刻切换成插入排序，而是先放一边，等整体的序列切成一个个未完全排序的子序列后，对整体序列进行一次插入排序。需要指出的是，这里插入排序处理的序列是半排序状态的序列，故不会产生O（N2）复杂度。
4、插入排序的优化，优化的空间是，去掉边界检查。
正常插入排序
void sort_insert(vector &vec, int len) //插入排序 { if (len <= 1) return; for (int i = 1; i < len; i++) { for (int j = i; j>0; j--) //j>0就是边界检查 { if (vec[j] < vec[j - 1]) swap(vec[j], vec[j - 1]); else break; //特别注意，之前没有写过这句代码 } }} 去掉边界检查的插入排序
void sort_insert(vector &vec, int len) //改进插入排序 { if (len <= 1) return; for (int i = 1; i < len; i++) { if (vec[i] 0; j--) { vec[j] = vec[j - 1]; } vec[0] = temp; } else //如果大于等于第一个元素，由于第一个元素的存在，使越界不可能出现，故省略越界检查 { for (int j = i;; j--) //略去j>0边界检查 { if (vec[j] < vec[j - 1]) swap(vec[j], vec[j - 1]); else break; //特别注意，之前没有写过这句代码 } } }} 注：为了简洁，删去了部分代码
templateinline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { if (__first != __last) { std::__introsort_loop(__first, __last, std::__lg(__last - __first) * 2); //对序列进行大部分的排序处理 std::__final_insertion_sort(__first, __last); //对未完全排序的序列进行插入排序 } }
template优化后的插入排序void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit) { while (__last - __first > int(_S_threshold)) //如果子序列不大于阈值，则不进行处理 { if (__depth_limit == 0) //超过递归深度，调用 partial_sort（用堆排序实现的函数，具体见上篇博客） { _GLIBCXX_STD_A::partial_sort(__first, __last, __last); return; } --__depth_limit; _RandomAccessIterator __cut = std::__unguarded_partition_pivot(__first, __last); std::__introsort_loop(__cut, __last, __depth_limit); __last = __cut; } }
templatevoid __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last) { if (last - first > __stl_threshold) { __insertion_sort(first, first + __stl_threshold); //在初始会考虑边界条件 /*//由于确认区间左侧边界，肯定存在比该区间所有值都小（或大），故肯定不会越界, 所以可以省去越界检查，整体的效率可以得到提升 */ __unguarded_insertion_sort(first + __stl_threshold, last); } else __insertion_sort(first, last);}
templatevoid __unguarded_linear_insert(RandomAccessIterator last, T value) { RandomAccessIterator next = last; --next; while (value < *next) { *last = *next; last = next; --next; } *last = value;}template inline 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_insert(last, value);}template 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));}
转载地址：http://oxwtb.baihongyu.com/