本文转载自微信公众号“后端研究院”，作者大白鸡。转载本文请联系后端研究院公众号。前言今天就来了解一下STL中排序算法的底层实现和代码技巧。众所周知，STL使用模板来支持数据结构和算法的泛化。泛化对于C++用户来说已经是一个惊喜，但是如果你看看STL开发者的强大阵容，你就会体会到STL给我们带来了什么。惊喜永远不会止于泛化。强大的性能和效率是STL最令人惊叹的特点。STL极致性能的背后，是大师们纯熟的编程功底和追求极致的工匠精神的真实体现。笔者能力有限，只能站在前辈们的肩膀上，和大家一起看看STL中排序算法背后到底隐藏着什么。有没有的既视感呢？让我们开始今天的排序算法之旅吧！自省哲学在了解排序算法的实现之前，我们先来看一个概念：自省排序。说实话，作者的语言水平真的一般。总觉得这个词用在排序算法上不太清楚，所以研究一下看看吧！内省排序英文是IntrospectiveSort，introspective这个词就是内省的意思，但是我还是不太明白。继续搜索看百度百科对这个词条的解释：Introspectioninpsychology，是心理学的基本研究方法之一。内省也叫自我观察。它是我们自己意识的一种内在的、主观的现象。也可以说是对自己主观体验及其变化的观察。由于其主观性，自古以来，内省一直是心理学界争论不休的话题。另外，内省也可以看作是自我反省，这也是儒家所强调的自我反省。从这个角度来说，可以应用到计算机领域，比如Java自省机制，cocoa自省机制。好家伙，原来自省是一个心理学术语，笔者在这里也有些感触。内省是自我反省、自我思考，根据自己的主观经验观察变化并进行调整，不寄希望于外界，而寄希望于自身的经验和能力。通俗地说，内省算法不挑数据集，尽量对每个数据集给出相应的处理方法，这样排序才有时间保证。写到这里，《倚天屠龙记》中张无忌大战六宗的场景浮现在脑海。不管敌人是强是弱，我都会用我的方式来应对。由他强，清风吹山；他被他横着，明月照在江面上。---《九阳真经》达摩的哲学，确实如此，我们换个整理的角度，看看内省的过程是怎样的。我理解的内省排序算法不依赖于外部数据的好坏，而是根据每一个极端场景做出相应的判断和决策调整，从而适应各种数据集，表现出优异的性能。内省排序俗话说，侠士讲究刀枪刀戟斧钺钺钩叉叉等多种兵器。这也告诉我们一个道理，没有武器是无敌的，只是在某些场景下是无敌的。优势，这就像软件工程中没有银弹一样。回到我们的排序算法，排序算法也可谓百花齐放：冒泡排序、选择排序、插入排序、快速排序、堆排序、桶排序等等。虽然老一代的一批排序算法都是O(n^2)，优秀的算法可以达到O(nlogn)，但是即使是nlogn的快排和堆排序也各有优缺点。插入排序在数据几乎有序的场景下性能可以达到O(n)。有时候我们要做的不是冲突比较，而是融合创新。内省排序是DavidMusser于1997年设计的一种排序算法。这种排序算法首先从快速排序开始。当递归深度超过一定深度（深度为已排序元素个数的对数值）时，切换到堆排序。DavidMusser是STL领域的知名人物。不管在什么语境下，盲目比较好坏是没有意义的。自省排序是高手。为了使排序算法达到全面而优异的性能，自省排序算法结合了快速排序、堆排序和插入排序，根据当前数据集的特点选择使用哪种排序算法，使得每个算法可以展现自己的实力。这个想法真的很鼓舞人心。自省排序的编排前面说了自省排序主要结合了快速排序、堆排序和插入排序，那么不禁要问，这三种排序是怎么排兵布阵的呢？一起来看看三种排序的优缺点吧！快速排序在数据量大的时候无论是有序还是重复都可以通过优化算法达到O(nlogn)。虽然堆排序也是O(nlogn)，但由于某些原因它很快。排序会更快。当递归深度分割严重不均匀时，会退化到O(n^2)复杂度，此时性能会打折扣。这是快速排序的缺点。堆排序堆排序是快速排序的有力竞争者。最大的特点是可以达到O(nlogn)，复杂度很稳定。它不会像快排那样退化到O(n^2)，但是在堆排序的过程中会涉及到大量的堆调整，元素比较是跳跃式的。Cache的局部性没有得到很好的利用，以及其他一些原因导致堆排序比快速排序慢，但是大O复杂度还是在一个水平上。插入排序的一个特点就是我们在打牌的时候，在对我们手中的牌进行排序的时候，如果已经是有序的，我们只需要做很少的调整。因此，插入排序在数据量小且几乎有序的情况下，复杂度可以降低到O(n)，值得应用。优缺点也大致清楚了，大家可以猜猜自省排序在实践中是如何调度这三种排序算法的：排序，复杂度可以在O(nlogn)操作的深层，在快速排序的递归过程中，会涉及到很多栈帧保存、切换等递归操作。如果分割不当，递归过深，栈溢出程序可能会终止。因此，如果快速排序过程退化到O(n^2)，此时，它会自动检测并切换到堆排序，因为堆排序并没有退化，可以稳定在O(nlogn)。当元素个数小于某个经验设定值时（可以认为是递归即将结束前的前几步），数据实际上几乎是有序的。这时候可以使用插入排序来提高效率，进一步降低复杂度到O(n)。写到这里，笔者又想到了另外一个场景：2005年春晚小品黄宏龚汉林在《装修》中扮演的黄宏作为一名装修工人，手持一大一小两把铁锤，一把80的大锤和一把40的小锤子。锤头切换使用。其实切换排序算法和自省排序是同一个道理，所以技术来源于生活又高于生活。一起来一张图感受下：用了很多篇幅讲反省思考和反省排序。相信大家都已经掌握了，下面就来详细看看实现细节吧。这是本文的重点。一起继续分析吧！排序算法的实现细节本文介绍的排序算法是基于SGISTL版本的，主要是基于侯捷老师的书《STL源码剖析》的蓝图，所以使用的是没有函子的版本.一起来欣赏大牛们的佳作吧！图为作者买了很久却一直按在框底的STL书：sort函数的应用场景SGISTL中sort的参数是两个随机访问迭代器RandomAccessIterator，以及的模板sort也是基于这个迭代器，所以如果容器不是随机访问迭代器，一般的sort函数可能用不上。associativecontainermapandset底层是基于RB-Tree的，RB-Tree已经有自己的顺序，所以不需要使用sort算法。序列容器list是双向迭代器不是随机访问迭代器，而vector和deque是随机访问迭代器适用于排序算法的容器适配器stack、queue、priority-queue是限制元素顺序的容器，所以排序算法不适用。综上所述，我们可以知道排序算法可以很好地应用于vector和deque容器。sort总览前面介绍了自省排序，下面我们一步步看看sort是如何使用introsort的。前面的入口代码：templateinlinevoidsort(RandomAccessIteratorfirst,RandomAccessIteratorlast){if(first!=last){__introsort_loop(first,last,value_type(first),__lg(last-first)*2);__final_insertion_sort(first,last);}}从代码来看，sort使用了两个随机访问迭代器first和last，作为待排序序列的开始和结束，进一步调用了两个函数__introsort_loop和__final_insertion_sort，从字面上看前者是一个自省排序循环，后者是插入排序。我注意到__introsort_loop的第三个参数，__lg(last-first)*2，根据我们的经验猜测，应该是限于递归的深度，不用担心代码实现：templateinlineSize__lg(sizen){Sizek;for(k=0;n>1;n>>=1)++k;returnk;}这段代码的意思是n=last-first，2^k<=nk值的最大整数。所以总体来说，假设last-first=20，k=4时，最大分割深度depth_max=4*2=8，所以我们可以根据first和last来确定递归的最大深度。快速排序和堆排序的配合__introsort_loop函数主要封装了快速排序和堆排序，我们来看看这个函数的实现细节：//排序函数入口templatevoid__introsort_loop(RandomAccessIteratorfirst,RandomAccessIteratorlast,T*,Sizeddepth_limit){while(last-first>__stl_threshold){if(depth_limit==0){partial_sort(first,last,last);//使用堆排序return;}--depth_limit;//减去拆分平衡RandomAccessIteratorcut=__unguarded_pa??rtition(first,last,T(__median(*first,*(first+(last-first)/2),*(last-1))));//三点中位数划分过程__introsort_loop(cut,last,value_type(first),depth_limit);//子序列递归调用last=cut;//迭代器交换切换到左序列}}//基于三点中值法的分区算法枢轴){while(true){while(*first0还有个分裂余额，闲着无聊！于是我们来到了__unguarded_pa??rtition，这个函数从字面上看就是快速排序的partiton过程，返回切出的随机访问迭代器。__unguarded_pa??rtition的第三个参数__median使用三点中值法得到的基准值Pivot。至此，快速排序的分区的三个元素就收集完了。,最后回到新的切点位置；继续看，很快就搞定了，出现了__introsort_loop，而且是递归的。特别注意这里只有一个递归，输入是cut和last，相当于右子序列，左子序列怎么办？不要急着往下看。last=cut转为cut，成为左子序列的右边界，开始处理左子序列；快速排序的实现与前面提到的sort中快速排序的写法进行对比。与我们之前看到的有一些不同。看完《STL源码剖析》是如何处理quicksort的左序列的，侯杰老师写道：“写法可读性差，效率也不见得好”，看到这里更是一头雾水，还是试着分析一下吧！图为：侯捷老师在STL源码分析中对这种写法的点评。pivot=func(arr);//使用某种方法得到参考值cut=partition(left,right,pivot);//左右边界和参考值来了联合确定分割点位置quicksort(arr,left,cut-1);//递归处理左序列quicksort(arr,cut+1,right);//递归处理右序列}SGISTL中的写法：stl_quicksort(first,last){//作为外层控制结构循环while(ok){cut=stl_partition(first,last,_median(first,last));//拆分分区stl_quicksort(cut,last);//递归calltoprocesstherightchildSequencelast=cut;//cut赋值到last相当于切换到左边的子序列然后继续循环}}网上有一些大牌的文章说快排的方法在sgistl中借助while循环省去了左序列的一半调用递归调用是典型的尾递归优化思想。这里我还没有写测试代码来做对比。我就先走坑写个对比测试，再评论。不过，你可以看看这种sgi的写法。堆排序细节//注意：这是一个带有自定义比较功能的堆排序版本//堆和堆顶操作模板void__partial_sort(RandomAccessIteratorfirst,RandomAccessIteratormiddle,RandomAccessIteratorlast,T*,Comparecomp){make_heap(first,middle,comp);for(RandomAccessIteratori=middle;iinlinevoidpartial_sort(RandomAccessIteratorfirst,RandomAccessIteratormiddle,RandomAccessIteratorlast,Comparecomp){__partial_sort(first,middle,last,value_type(first),comp);}插入排序发挥作用__introsort_loop达到__stl_threshold阈值后，可以认为数据集已经差不多有序了。这时候可以使用插入排序进一步提高排序速度，也避免了递归带来的系统消耗，看__final_insertion_sort的具体实现：>__stl_threshold){__insertion_sort(第一个,第一个+__stl_threshold);__unguarded_insertion_sort(first+__stl_threshold,last);}else__insertion_sort(first,last);}下面分析一下__final_insertion_sort的实现细节：引入参数随机访问迭代器first和last如果last-first>__stl_threshold不成立，调用__insertion_sort，这是相当于比较少的元素，不需要特殊处理就可以直接调用；如果last-first>__stl_threshold成立，则进一步分为两部分，分别调用__insertion_sort和__unguarded_insertion_sort。两部分的分割点是__stl_threshold，这是必然的请问这两个函数有什么区别？__insertion_sort的实现//调整逆序模板void__unguarded_linear_insert(RandomAccessIteratorlast,Tvalue){RandomAccessIteratornext=last;--next;while(value<*next){*last=*next;last=next;--next;}*last=value;}templateinlinevoid__linear_insert(RandomAccessIteratorfirst,RandomAccessIteratorlast,T*){Tvalue=*last;if(value<*first){copy_backward(first,last,last+1);//intervalmovement*first=value;}else__unguarded_linear_insert(last,value);}//__insertion_sort入口模板void__insertion_sort(RandomAccessIteratorfirst,RandomAccessIteratorlast){if(first==last)return;for(RandomAccessIteratori=first+1;i!=last;++i)__linear_insert(first,i,value_type(first));}也出现在insert函数中__unguarded_xxx形式的函数，unguarded这个词的意思是不受保护，不受保护。侯捷提到，这种函数形式是在一定条件下无需边界测试条件也能正确运行的函数。copy_backward也是一个函数整体移动的优化避免了一个一个的调整移动，底层调用memmove高效实现。__unguarded_insertion_sort实现模板void__unguarded_insertion_sort_aux(RandomAccessIteratorfirst,RandomAccessIteratorlast,T*){for(RandomAccessIteratori=first;i!=last;++i)__unguarded_linear_insert(i,T(*iAccess));}templateinlinevoid__unguarded(RandomAccessIteratorfirst,RandomAccessIteratorlast){__unguarded_insertion_sort_aux(first,last,value_type(first));}关于插入排序这两个函数的实现和用途，展开的时候会很详细，所以想着后面单独写插入排序我单独拿出来详细研究，本文暂不深究。有兴趣的读者可以先阅读相关资料，稍后我们一起论证！总结本文主要阐述自省排序的思想和基本实现思路。并以此为出发点，对sgistl中排序算法的实现做了一些解读。stl的作者为了追求极致的性能，使用了很多技巧。本文不展开太多，主要原因是等级不要太高，以免误读。聪明的读者可以试着分析一下大牛。技能的巅峰之作。
