深入理解快速排序和STL的sort算法

590次阅读  |  发布于4年以前

1.写在前面

通过本文你将了解到以下内容：

  1. 那年初识快排

2.1 看似青铜实则王者

常见不等同于简单。

很多人提起快排和二分都觉得很容易的样子，但是让现场Code很多就翻车了，就算可以写出个递归版本的代码，但是对其中的复杂度分析、边界条件的考虑、非递归改造、代码优化等就无从下手，填鸭背诵基本上分分钟就被面试官摆平了。

快速排序Quicksort又称划分交换排序partition-exchange sort，简称快排，一种排序算法。最早由C. A. R. Hoare教授在1960年左右提出，在平均状况下，排序n个项目要O(nlogn)次比较。

在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

快排的提出者是大名鼎鼎的人物，go语言使用的并发模型CSP也是这个大神提出的，一起膜拜下。

查尔斯·安东尼·理查德·霍尔爵士(Sir Charles Antony Richard Hoare缩写为C. A. R. Hoare，1934年1月11日－），昵称为东尼·霍尔(Tony Hoare)，生于大英帝国锡兰可伦坡（今斯里兰卡），英国计算机科学家，图灵奖得主。

他设计了快速排序算法、霍尔逻辑、交谈循序程式。在操作系统中，他提出哲学家就餐问题，并发明用来作为同步程序的监视器（Monitors）以解决这个问题。他同时证明了监视器与信号标（Semaphore）在逻辑上是等价的。

1980年获颁图灵奖、1982年成为英国皇家学会院士、2000年因为他在计算机科学与教育方面的杰出贡献，获得英国王室颁赠爵士头衔、2011年获颁约翰·冯诺依曼奖，现为牛津大学荣誉教授，并在剑桥微软研究院担任研究员。

2.2 快速排序的基本思想和过程

2.2.1 D&C分治思想

在计算机科学中，分治法(Divide&Conquer)是建基于多项分支递归的一种很重要的算法范式，快速排序是分治思想在排序问题上的典型应用。

所谓分治思想D&C就是把一个较大规模的问题拆分为若干小规模且相似的问题。再对小规模问题进行求解，最终合并所有小问题的解，从而形成原来大规模问题的解。

字面上的解释是"分而治之"，这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、傅立叶变换（快速傅立叶变换）。

分治法中最重要的部分是循环递归的过程，每一层递归有三个具体步骤：

2.2.2 基本过程

快速排序使用分治法来把一个序列分为小于基准值和大于基准值的两个子序列。递归地排序两个子序列，直至最小的子序列长度为0或者1，整个递归过程结束，详细步骤为：

  1. 快速的递归实现和迭代实现

快速排序一般大家写递归的时候更多，但是递归往往也会写出不同风格的版本，所以我们一起来看下多个风格的递归版本和迭代版本的实现，多种代码对比会让我们理解更深刻。

3.1 递归实现代码

C语言递归版本一：

C++递归版本二：

两个版本均可正确运行，但代码有一点差异:

3.2 递归实现过程演示

过程说起来比较抽象，稳住别慌！灵魂画手画图来演示这两个过程。

3.2.1 C版本一过程演示

以第一次递归循环为例:

步骤1: 选择第一个元素为基准值pivot=a[left]=5,right指针指向尾部元素，此时先由right自右向左扫描直至遇到<5的元素，恰好right起步元素4<5，因此需要将4与5互换位置；

步骤2: 4与5互换位置之后，轮到left指针从左向右扫描，注意一下left的起步指针指向了由步骤1交换而来的4，新元素4不满足停止条件，因此left由绿色虚箭头4位置游走到元素9的位置，此时left找到9>5，因此将此时left和right指向的元素互换，也就是元素5和元素9互换位置；

步骤3: 互换之后right指针继续向左扫描，从蓝色虚箭头9位置游走到3的位置，此时right发现3<5，因此将此时left和right指向的元素互换，也就是元素3和元素5互换位置；

步骤4: 互换之后left指针继续向右扫描，从绿色虚箭头3位置游走到6的位置，此时left发现6>5，因此将此时left和right指向的元素互换，也就是元素6和元素5互换位置；

步骤5: 互换之后right指针继续向左扫描，从蓝色虚箭头6位置一直游走到与left指针相遇，此时二者均停留在了pivot=5的新位置上，且左右两边分成了两个相对于pivot值的子序列；

循环结束：至此出现了以5为基准值的左右子序列，接下来就是对两个子序列实施同样的递归步骤。

以第二次和第三次左子序列递归循环为例:

步骤1-1：选择第一个元素为基准值pivot=a[left]=4，right指针指向尾部元素，此时先由right指针向左扫描，恰好起步元素3<4，因此将3和4互换；

步骤1-2：互换之后left指针从元素3开始向右扫描，一直游走到与right指针相遇，此时本次循环停止，特别注意这种情况下可以看到基准值4只有左子序列，无右子序列，这种情况是一种退化，就像冒泡排序每次循环都将基准值放置到最后，因此效率将退化为冒泡的O(n^2);

步骤1-3：选择第一个元素为基准值pivot=a[left]=3，right指针指向尾部元素，此时先由right指针向左扫描，恰好起步元素1<3，因此将1和3互换；

步骤1-4：互换之后left指针从1开始向右扫描直到与right指针相遇，此时注意到pivot=3无右子序列且左子序列len=1，达到了递归循环的终止条件，此时可以认为由第一次循环产生的左子序列已经全部有序。

循环结束：至此左子序列已经排序完成，接下来对右子序列实施同样的递归步骤，就不再演示了，聪明的你一定get到了。

特别注意:

以上过程中left和right指针在某个元素相遇，这种情况在代码中是不会出现的，因为外层限制了i!=j，图中之所以放到一起是为了直观表达终止条件。

3.2.2 C++版本二过程演示

分析一下:

个人觉得这个版本虽然同样使用D&C思想但是更加简洁，从动画可以看到选择pivot=a[end]，然后左右指针分别从index=0和index=end-1向中间靠拢。

过程中扫描目标值并左右交换，再继续向中间靠拢，直到相遇，此时再根据a[left]和a[right]以及pivot的值来进行合理置换，最终实现基于pivot的左右子序列形式。

脑补场景:

上述过程让我觉得很像统帅命令左右两路军队从两翼会和，并且在会和过程中消灭敌人有生力量(认为是交换元素)，直到两路大军会师。

此时再将统帅王座摆到正确的位置，此过程中没有统帅王座的反复变换，只有最终会师的位置，以王座为中心形成了左翼子序列和右翼子序列，再重复相同的过程，直至完成大一统。

脑补不过瘾 于是凑图一张:

3.3 多种递归版本说明

虽然快排的递归版本是基于D&C实现的，但是由于pivot值的选择不同、交换方式不同等诸多因素，造成了多种版本的递归代码。

并且内层while循环里面判断>=还是>(即是否等于的问题)，外层循环判断本序列循环终止条件等写法都会不同，因此在写快排时切忌死记硬背，要不然边界条件判断不清楚很容易就死循环了。

看下上述我贴的两个版本的代码核心部分：

另外在网上很多大神的博客里面还进行了多种模式的快排：单轴模式、双向切分、三项切分、多基准值等新花样，感兴趣可以参考快速排序算法的多种实现。

其实无论哪种写法都需要明确知道自己是交换、还是覆盖、基准值选取位置、>=和<=的等号问题、循环终止条件等，这样才能写出BugFree的快速排序算法。

网上很多代码的核心部分是这样写的：

覆盖or交换

代码中首先将pivot的值引入局部变量保存下来，这样就认为A[L]这个位置是个坑，可以被其他元素覆盖，最终再将pivot的值填到最后的坑里。

这种做法也没有问题，因为你只要画图就可以看到，每次坑的位置是有相同元素的位置，也就是被备份了的元素。

个人感觉 与其叫坑不如叫备份，但是如果你代码使用的是基于指针或者引用的swap，那么就没有坑的概念了。

这就是覆盖和交换的区别，本文的例子都是swap实现的，因此没有坑位被最后覆盖一次的过程。

3.4 迭代版本实现

所谓迭代实现就是非递归实现一般使用循环来实现，我们都知道递归的实现主要是借助系统内的栈来实现的。

如果调用层级过深需要保存的临时结果和关系会非常多，进而造成StackOverflow栈溢出。

Stack一般是系统分配空间有限内存连续速度很快，每个系统架构默认的栈大小不一样，笔者在x86-CentOS7.x版本使用ulimit -s查看是8192Byte。

避免栈溢出的一种办法是使用循环，以下为笔者验证的使用STL的stack来实现的循环版本，代码如下：

  1. 快速排序的优化

快速排序是图领奖得主发明的算法，被誉为20世纪最重要的十大算法之一，快速排序为了可以在多种数据集都有出色的表现，进行了非常多的优化，因此对我们来说要深入理解一种算法的最有效的手段就是不断优化提高性能。

4.1 快速排序vs归并排序

快速排序和归并排序采用的基本思想都是分治思想Divide&Conquer，从D&C思想来看最主要的部分就是分割和合并，两种算法在使用D&C时侧重点有一些差异:

归并排序在分割时处理很简单，在合并时处理比较多，重点在合并。

快速排序在分割时处理比较复杂，由于交换的存在递归结束时就相当于合并完成了，重点在分割。

归并排序分治示意图：

快速排序分治示意图：

注:快排的过程就不写具体的数字了 仅为达意 点到即可。

可以明显看出来，快速排序在选择基准值时对整个分治过程影响很大，因为下一个环节的分治是基于前一环节的分割结果进行的。

4.2 分区不均匀和最坏复杂度

4.2.1 极端分区

考虑一种极端的情况下，如果基准值选取的不合理，比如是最大的或者最小的，那么将导致只有一边有数据，对于已经排序或者近乎有序的数据集合来说就可能出现这种极端情况，还是来画个图看下：

图中展示了每次分治都选择第一个元素作为基准值，但是每次的基准值都是最小值，导致每次基准值左侧没有子序列，除了基准值之外全部元素都在右子序列。

4.2.2 最坏情况概率和复杂度计算

每次分割排序之后，只能在有序序列中增加1个元素递归树变成了单支树并且递归深度变大，极端情况的出现概率和最坏复杂度计算如下：

极端情况概率就是每次在剩余所有元素中挑出最小的，这样每次的概率都是1/(n-i)，所以组合起来就是1/(n!)，所以随机数据集合出现最差情况的概率非常低，但是有序数据下固定基准值选择就可能造成极端情况的出现。

最坏复杂度相当于每次从n-i个元素中只找到1个数据，将所有情况累加也就达到了O(n^2)级别，并不是递归过程全都挑选了最值作为基准值才会出现O(n^2)的复杂度，复杂度是一个概率化的期望值，具体的系数不同影响也很大。

4.3 基准值选取优化

分割越均匀速度越快

从上面的几张图可以清晰看到基准值的不同对于D&C过程的分割会产生很大的影响，为了保证快速排序的在通用数据集的效率，因此我们需要在基准值的选取上做一些决策，换句话说就是让选取的基准值每次都可以尽可能均匀地分割数据集，这样的效率是最高的。

随机选取基准值

网上有很多选择方法比如固定选取第一个、固定选取最后一个、固定选择中间值、三值平均选取等，不过个人觉得每一次都随机选取某个位置的数据作为基准值，然后与第一个值互换，这样就相当于每次的基准值都是随机选择的，就将固定index带来的问题，大大降低了。

随机vs固定对比试验

接下来做一组对比试验，生成一个0-100000的有序数组，代码增加了很多选择项和时间测量代码，测试代码如下：

笔者使用相同的数据集在fix和random模式下，后者的耗时明显低于前者，所以某些场景下随机化带来的性能提升很明显，是一个惯用的优化方法。

4.4 三分区模式优化

前面的路子都是以基准值为准分为小于子序列和大于子序列，考虑一种特殊的数据集，数据集中有大量重复元素，这种情况下使用两分区递归会对大量重复元素进行处理。

一个优化的方向就是使用三分区模式：小于区间、等于区间、大于区间,这样在后续的处理中则只需要处理小于区和大于区，降低了等于基准值区间元素的重复处理，加速排序过程。

4.4.1 三分区原理

如图为三分区模式中某个时刻的快照，其中展示了几个关键点和区间，包括基准值、小于区、等于区、处理值、待处理区、大于区。

在实际过程中根据处理值与基准值的大小关系，进行相应分区合并和交换，再进行下标移动就可以了，实际中分三种情况，这也是写代码的依据：

  1. 处理值e==p，将e合并到等于区，i++；
  2. 处理值e<p，将e与(lt+1)位置的数据交换，扩展小于区lt++，等于区长度不变，相当于整体平移；
  3. 处理值e>p，将e与(gt-1)位置的数据交换，扩展大于区gt--，此时i不变，交换后的值是之前待处理区的尾部数据；

处理完待处理区的全部数据之后的调整也非常重要，主要是将基准值P与lt位置的数据交换，从而实现最终的三分区，如图所示：

从最终的分区可以看到，我们下一次的循环可以不处理等于区的数据而只处理两端分区数据，这样在大量重复场景下优化效果会非常明显。

4.4.2 三分区实验

笔者使用相同的数据集在二分区模式下测试10w数据规模耗时大约是1800ms，数据集减少10倍耗时却增大了几十倍，或许二分区代码还是存在优化空间，不过这个对比可以看到存在大量重复元素时三分区性能还是很不错的。

4.5 快排优化小结

对快速排序的优化主要体现在基准值选取、数据集分割、递归子序列选取、其他排序算法混合等方面，换句话说就是让每次的分区尽量均匀且没有重复被处理的元素，这样才能保证每次递归都是高效简洁的。

  1. STL的sort算法

在了解sort算法的实现之前先来看一个概念：内省式排序，说实话笔者的语文水平确实一般，对于这个词语用在排序算法上总觉得不通透，那就研究一下吧！

5.1 内省思想

内省式排序英文是Introspective Sort，其中单词introspective是内省型的意思，还是不太明白，继续搜索，看一下百度百科对这个词条的解释：

内省（Introspection ）在心理学中，它是心理学基本研究方法之一。内省法又称自我观察法。它是发生在内部的，我们自己能够意识到的主观现象。也可以说是对于自己的主观经验及其变化的观察。

正因为它的主观性，内省法自古以来就成为心理学界长期的争论。另外内省也可看作自我反省，也是儒家强调的自我思考。从这个角度说可以应用于计算机领域，如Java内省机制和cocoa内省机制。

From 百度百科-内省-科普中国审核通过词条

原来内省是个心理学名词，到这里笔者有些感觉了，内省就是自省、自我思考、根据自己的主观经验来观察变化做出调整，而不是把希望寄托于外界，而是自己的经验和能力。

通俗点说，内省算法不挑数据集，尽量针对每种数据集都能给定对应的处理方法，让排序都能有时间保证。写到这里，让笔者脑海浮现了《倚天屠龙记》里面张无忌光明顶大战六大门派的场景，无论敌人多么强悍或者羸弱，我都按照自己的路子应对。

原来内省是个心理学名词，到这里笔者有些感觉了，内省就是自省、自我思考、根据自己的主观经验来观察变化做出调整，而不是把希望寄托于外界，而是自己的经验和能力。

通俗点说，内省算法不挑数据集，尽量针对每种数据集都能给定对应的处理方法，让排序都能有时间保证。写到这里，让笔者脑海浮现了《倚天屠龙记》里面张无忌光明顶大战六大门派的场景，无论敌人多么强悍或者羸弱，我都按照自己的路子应对。

5.2 内省排序概况

俗话说侠者讲究刀、枪、剑、戟、斧、钺、钩、叉等诸多兵器，这也告诉我们一个道理没有哪种兵器是无敌的，只有在某些场景下的明显优势，这跟软件工程没有银弹是一样的。

回到我们的排序算法上，排序算法也可谓是百花齐放：冒泡排序、选择排序、插入排序、快速排序、堆排序、桶排序等等。

虽然一批老一辈的排序算法是O(n^2)的，优秀的算法可以到达O(nlogn)，但是即使都是nlogn的快速排序和堆排序都有各自的长短之处，插入排序在数据几乎有序的场景下性能可以到达O(n)，有时候我们应该做的不是冲突对比而是融合创新。

内省排序是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序,David Musser大牛是STL领域响当当的人物。

抛开语境一味地对比孰好孰坏其实都没有意义，内省式排序就是集大成者，为了能让排序算法达到一个综合的优异性能，内省式排序算法结合了快速排序、堆排序、插入排序，并根据当前数据集的特点来选择使用哪种排序算法，让每种算法都展示自己的长处，这种思想确实挺启发人的。

5.3 内省排序排兵布阵

前面提到了内省式排序主要结合了快速排序、堆排序、插入排序，那么不禁要问，这三种排序是怎么排兵布阵的呢？知己知彼百战不殆，所以先看下三种排序的优缺点吧！

优缺点也大致清楚了，所以可以猜想一下内省式排序在实际中是如何调度使这三种排序算法的：

5.4 sort算法细节

本文介绍的sort算法是基于SGI STL版本的，并且主要是以侯捷老师的《STL源码剖析》一书为蓝本来进行展开的，因此使用了不带仿函数的版本。

SGI STL中的sort的参数是两个随机存取迭代器RandomAccessIterator，sort的模板也是基于此种迭代器的，因此如果容器不是随机存取迭代器，那么可能无法使用通用的sort函数。

综上我们可以知道，sort算法可以很好的适用于vector和deque这两种容器。

前面介绍了内省式排序，所以看下sort是怎么一步步来使用introsort的，上一段入口代码：

从代码来看sort使用了first和last两个随机存取迭代器，作为待排序序列的开始和终止，进一步调用了__introsort_loop和__final_insertion_sort两个函数，从字面上看前者是内省排序循环，后者是插入排序。其中注意到__introsort_loop的第三个参数__lg(last - first)*2，凭借我们的经验来猜(蒙)一下吧，应该递归深度的限制，不急看下代码实现：

这段代码的意思就是n=last-first，2^k<=n的最大整数k值。

所以整体看当假设last-first=20时，k=4,最大分割深度depth_max=4*2=8，从而我们就可以根据first和last来确定递归的最大深度了。

快速排序和堆排序的配合

__introsort_loop函数中主要封装了快速排序和堆排序，来看看这个函数的实现细节：

各位先不要晕更不要蒙圈，一点点分析肯定可以拿下的。

快速排序的实现对比

前面提到了在sort中快速排序的写法和我们之前见到的有一些区别，看了一下《STL源码剖析》对快排左序列的处理，侯捷老师是这么写的："写法可读性较差，效率并没有比较好"，看到这里更蒙圈了，不过也试着分析一下吧！

图为：**STL源码剖析中侯捷老师对该种写法的注释**

常见写法：

SGI STL中的写法:

网上有一些大佬的文章说sgi stl中快排的写法左序列的调用借助了while循环节省了一半的递归调用，是典型的尾递归优化思路.

这里我暂时还没有写测试代码做对比，先占坑后续写个对比试验，再来评论吧，不过这种sgi的这种写法可以看看哈。

堆排序的细节

//注：这个是带自定义比较函数的堆排序版本
//堆化和堆顶操作
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 < last; ++i)
        if (comp(*i, *first))
            __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
    sort_heap(first, middle, comp);
}
//堆排序的入口
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);
}

插入排序上场了

__introsort_loop达到__stl_threshold阈值之后，可以认为数据集近乎有序了，此时就可以通过插入排序来进一步提高排序速度了，这样也避免了递归带来的系统消耗，看下__final_insertion_sort的具体实现：

template <class RandomAccessIterator>
void __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);
}

来分析一下__final_insertion_sort的实现细节吧！

__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);
}

//__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));
}

在插入函数中同样出现了__unguarded_xxx这种形式的函数，unguarded单词的意思是无防备的，无保护的，侯捷大大提到这种函数形式是特定条件下免去边界检验条件也能正确运行的函数。

copy_backward也是一种整体移动的优化，避免了one by one的调整移动，底层调用memmove来高效实现。

__unguarded_insertion_sort的实现
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));
}

关于插入排序的这两个函数的实现和目的用途，展开起来会很细致，所以后面想着单独在写插入排序时单独拿出了详细学习一下。

6.写在最后

忙碌的日子里自己的时间就变得很少，然后开始思考未来，其实这样并不好。

不多说了，感谢各位读者的倾情阅读，笔芯你们。

巨人的肩膀

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8