标签：深度 iterator 子序列 http median 算法 使用 长度 超过
稍微花了一点点时间看了一下老师推荐的博客：http://feihu.me/blog/2014/sgi-std-sort/，看完后无不赞叹STL追求效率之极致，STL的sort排序算法综合了三种排序快排，堆排和插入排序，被称为Introspective Sort（内省式排序），在算法内部根据自身不同的情形来判断来使用不同的算法进行排序，sort算法可以说综合了三种排序算法的优点，追求效率到了极致。
一开始sort算法有两部分组成，__introsort_loop和__final_insertion_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);
//std::sort的最后一步——插入排序。
__final_insertion_sort(first, last);
}
}
__introsort_loop即是Introspective Sort内省式排序，__final_insertion_sort是插入排序。首先讲内省式排序即sort算法的大头。
template class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last, T*,Size depth_limit)
{
while (last - first > __stl_threshold) {
//depth_limit是前面所提到的判断分割行为是否有恶化倾向的阈值
if (depth_limit == 0) {
//函数调用partial_sort，它便是堆排序
partial_sort(first, last, last);
return;
}
--depth_limit;
RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first) / 2), *(last - 1))));
__introsort_loop(cut, last, value_type(first), depth_limit);
last = cut;
}
}
首先是while语句判断，last-first > __stl_threshold，__stl_threshold为最小分段阈值，值为16，大体上来说，当数据量很大时，Introspective Sort都是采用快速排序，也就是__unguarded_partition，当last-first
template class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value)
{
RandomAccessIterator next = last;
--next;
while (value next) {
*last = *next;
last = next;
--next;
}
*last = value;
}
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);
*first = value;
}
else
__unguarded_linear_insert(last, value);
}
__unguarded_linear_insert不对边界作检查。正因为如此，它一定比下面的__insertion_sort要快。那么为什么插入排序又可以分成无边界作检查和边界作检查呢。回到sort函数中的__final_insertion_sort函数进行分析。
template class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
//const int __stl_threshold = 16; 最小分段阈值
//一个带边界检查而另一个不带，不带边界检查的__unguarded_insertion_sort更快。
if (last - first > __stl_threshold) {
__insertion_sort(first, first + __stl_threshold);
__unguarded_insertion_sort(first + __stl_threshold, last);
}
else
//__insertion_sort和__unguarded_insertion_sort有何区别？
//有无边界检测
__insertion_sort(first, last);
}
我们发现如果区间大小last-first>16时将采用__insertion_sort和__unguarded_insertion_sort，__insertion_sort有边界检测插入排序区间是[first,first+16]，__unguarded_insertion_sort无边界检测插入排序区间是[first+17,last]，last-first
进一步分析，
我们首先只考虑最左边的子序列，先假设是由于第一种情况终止了这个函数，那么该子区域小于16。
因为使用的是快速排序，左边区间的所有数据一定比右边小，可以推断出最小值一定在该小于16的子区域内。
假设函数是第二种情况下终止，那么对于最左边的区间，由于递归深度过深，因此该区间会调用堆排序，所以这段区间的最小值一定位于最左端。
加上前面的分析：左边区间所有的数据一定比右边小，那么该区间内最左边的数据里一定有整个序列的最小值。
因此，不论是哪种情况，都可以保证起始的16个元素中一定有最小值。
如此便能够使用__insertion_sort对前16个元素进行排序，接着用__unguarded_insertion_sort毫无顾忌的在不考虑边界的情况下对剩于的区间进行更快速的排序。
写到这里，sort算法差不多分析完了，最后说一下感想，写代码要看作是雕琢一件艺术品，只有经过不断的打磨，才能在稳定性、安全性、通用性和效率上经历住考验，永远不要觉得自己写的代码已经到了完美了，要不断进行修改和优化，而且这个过程是不断进行的，只有不断追求卓越，才能到达顶峰。STL库积蓄了C++程序员们数十年的心血，里面的种种细节都值得我们去学习，学海无涯，书山有路，最后祝大家早日达成自己的理想。
#include const int __stl_threshold = 16;
template class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first, RandomAccessIterator last, T pivot) {
while (true)
{
while (*first first;
--last;
while (pivot last;
if (!(first return first;
iter_swap(first, last);
++first;
}
}
template class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, T*, Compare comp) {
make_heap(first, middle, comp);
for (RandomAccessIterator i = middle; i i)
if (comp(*i, *first))
__pop_heap(first, middle, i, T(*i), comp, distance_type(first));
sort_heap(first, middle, comp);
}
//partial_sort，堆排序
template class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp) {
__partial_sort(first, middle, last, value_type(first), comp);
}
//Introspective Sorting(内省式排序)
/*
该函数只有两种情况下可能返回,
一是区域小于等于阈值16；二是超过递归深度阈值。
我们现在只考虑最左边的子序列，先假设是由于第一种情况终止了这个函数，那么该子区域小于16。
再根据前面的结论：左边区间的所有数据一定比右边小，可以推断出最小值一定在该小于16的子区域内。
假设函数是第二种情况下终止，那么对于最左边的区间，由于递归深度过深，因此该区间会调用堆排序，所以这段区间的最小值一定位于最左端。
再加上前面的结论：左边区间所有的数据一定比右边小，那么该区间内最左边的数据一定是整个序列的最小值。
因此，不论是哪种情况，都可以保证起始的16个元素中一定有最小值。
如此便能够使用__insertion_sort对前16个元素进行排序，接着用__unguarded_insertion_sort毫无顾忌的在不考虑边界的情况下对剩于的区间进行更快速的排序。
*/
template class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last, T*,Size depth_limit)
{
//const int __stl_threshold = 16; 最小分段阈值
//当数据长度小于该阈值时，再使用递归来排序显然不划算，递归的开销相对来说太大。
//而此时整个区间内部有多个元素个数少于16的子序列，
//每个子序列都有相当程度的排序，但又尚未完全排序，过多的递归调用是不可取的。
//而这种情况刚好插入排序最拿手，它的效率能够达到O(N)。
//因此这里中止快速排序，sort会接着调用外部的__final_insertion_sort x行
while (last - first > __stl_threshold) {
//depth_limit是前面所提到的判断分割行为是否有恶化倾向的阈值
if (depth_limit == 0) {
//函数调用partial_sort，它便是堆排序
partial_sort(first, last, last);
return;
}
--depth_limit;
//__unguarded_partition，这其实就是我们平常所使用的快速排序主体部分，用于根据pivot将区间分割为两个子序列。
//__median函数，它的作用是取首部、尾部和中部三个元素的中值作为pivot。
//我们之前学到的快速排序都是选择首部、尾部或者中间位置的元素作为pivot，并不会比较它们的值，在很多情况下这将引起递归的恶化。现在这里采用的中值法可以在绝大部分情形下优于原来的选择。
RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first) / 2), *(last - 1))));
//递归结构
/*
可以看出它是一个递归函数，因为我们说过，Introspective Sort在数据量很大的时候采用的是正常的快速排序，
因此除了处理恶化情况以外，它的结构应该和快速排序一致。
但仔细看代码，先不管循环条件和if语句(它们便是处理恶化情况所用)，循环的后半部分是用来递归调用快速排序。
*/
//__introsort_loop中只有对右边子序列进行递归调用是不是？
//左边的递归不见了。的确，这里的写法可读性相对来说比较差，但是仔细一分析发现是有它的道理的，它并不是没有管左子序列。
//注意看，在分割原始区域之后，对右子序列进行了递归，接下来的last = cut将终点位置调整到了分割点，那么此时的[first, last)区间就是左子序列了。
//又因为这是一个循环结构，那么在下一次的循环中，左子序列便得到了处理。只是并未以递归来调用!
//两者区别就在于STL节省了接近一半的函数调用，由于每次的函数调用有一定的开销，因此对于数据量非常庞大时，这一半的函数调用可能能够省下相当可观的时间。
__introsort_loop(cut, last, value_type(first), depth_limit);
last = cut;
}
}
//__unguarded_linear_insert不对边界作检查。正因为如此，它一定比下面的__insertion_sort要快。
template class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value)
{
RandomAccessIterator next = last;
--next;
while (value next) {
*last = *next;
last = next;
--next;
}
*last = value;
}
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);
*first = value;
}
else
__unguarded_linear_insert(last, value);
}
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));
}
//可以忽略掉这层aux函数的包装，它只是为了获得迭代器所指向的类型，其实这两个函数可以合并为一个。
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));
}
template class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
__unguarded_insertion_sort_aux(first, last, value_type(first));
}
template class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
//const int __stl_threshold = 16; 最小分段阈值
//一个带边界检查而另一个不带，不带边界检查的__unguarded_insertion_sort更快。
if (last - first > __stl_threshold) {
__insertion_sort(first, first + __stl_threshold);
__unguarded_insertion_sort(first + __stl_threshold, last);
}
else
//__insertion_sort和__unguarded_insertion_sort有何区别？
//有无边界检测
__insertion_sort(first, last);
}
template class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
if (first != last) {
__introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
//std::sort的最后一步——插入排序。
__final_insertion_sort(first, last);
}
}
STL源码分析——sort排序
标签：深度 iterator 子序列 http median 算法 使用 长度 超过
原文地址：https://www.cnblogs.com/likeghee/p/11565503.html