来源：后端技术指南针
作者：后端技术指南针
苦逼的码农注：之前面试就被问过快速排序的优化，然而答的不好，所以关于快速排序的优化，还是要学一学啊。
前面的一篇文章【决战西二旗】|你真的懂快速排序？讲了快速排序的基本概念、核心思想、基础版本代码实现等，让我们对快速排序有了一个充分的认识，但还无法达到面试中对快速排序灵活应对的程度。
快速排序是图领奖得主发明的算法，被誉为20世纪最重要的十大算法之一，快速排序为了可以在多种数据集都有出色的表现，进行了非常多的优化，因此对我们来说要深入理解一种算法的最有效的手段就是不断优化提高性能。
如果面试中遇到快速排序的问题，那就要小心了，面试官出快排的题目基本上都是鸡贼地给你挖好坑等着你，所以我们要做到逢山开路遇水搭桥，要不然等着我们的大概就只有这个场景了：
废话不说直接上车 五道口大白号发车了！
滴！老年卡… 大熊你为啥又用你二大爷的卡...汗
通过本文你将了解到以下内容：
快速排序的分区过程
快速排序和归并排序采用的基本思想都是分治思想Divide&Conquer，从D&C思想来看最主要的部分就是，两种算法在使用D&C时侧重点有一些差异:
归并排序分治示意图
快速排序分治示意图
注:快排的过程就不写具体的数字了 仅为达意 点到即可。
可以明显看出来，快速排序在选择基准值时对整个分治过程影响很大，因为下一个环节的分治是基于前一环节的分割结果进行的。
快速排序划分不均匀情况
考虑一种极端的情况下，如果，那么将导致只有一边有数据，对于已经排序或者近乎有序的数据集合来说就可能出现这种极端情况，还是来画个图看下：
图中展示了每次分治都选择第一个元素作为基准值，但是每次的基准值都是最小值，导致每次基准值左侧没有子序列，除了基准值之外全部元素都在右子序列。
概率和复杂度计算
每次分割排序之后，只能在有序序列中增加1个元素，极端情况的出现概率和最坏复杂度计算如下：
极端情况概率就是每次在剩余所有元素中挑出最小的，这样每次的概率都是1/(n-i)，所以组合起来就是1/(n!)，所以随机数据集合出现最差情况的概率非常低，但是有序数据下固定基准值选择就可能造成极端情况的出现。
最坏复杂度相当于每次从n-i个元素中只找到1个数据，将所有情况累加也就达到了O(n^2)级别，并不是递归过程全都挑选了最值作为基准值才会出现O(n^2)的复杂度，复杂度是一个概率化的期望值，具体的系数不同影响也很大。
快速排序基准值选取优化
分割越均匀速度越快
从上面的几张图可以清晰看到，为了保证快速排序的在通用数据集的效率，因此我们需要在基准值的选取上做一些决策，换句话说就是让选取的基准值每次都可以，这样的效率是最高的。
随机选取基准值
网上有很多选择方法比如固定选取第一个、固定选取最后一个、固定选择中间值、三值平均选取等，不过个人觉得，这样就相当于每次的的，就将固定index带来的问题，大大降低了。
随机vs固定对比试验
接下来做一组对比试验，生成一个，代码增加了很多选择项和时间测量代码，测试代码如下：
笔者使用相同的数据集在fix和random模式下，后者的耗时只有前者的大约1/10，所以某些场景下随机化带来的性能提升很明显，是一个惯用的优化方法。
快速排序的三分区模式原理
前面的路子都是以基准值为准分为小于子序列和大于子序列，考虑一种特殊的数据集，数据集中有大量重复元素，这种情况下使用两分区递归会对大量重复元素进行处理。
一个优化的方向就是使用三分区模式：这样在后续的处理中则只需要处理小于区和大于区，降低了等于基准值区间元素的重复处理，加速排序过程。
如图为三分区模式中某个时刻的快照，其中展示了几个关键点和区间，包括基准值、小于区、等于区、处理值、待处理区、大于区。
在实际过程中根据处理值与基准值的大小关系，进行相应分区合并和交换，再进行下标移动就可以了，实际中分三种情况，这也是写代码的依据：
处理完待处理区的全部数据之后的调整也非常重要，主要是将基准值P与lt位置的数据交换，从而实现最终的三分区，如图所示：
从最终的分区可以看到，我们下一次的循环可以不处理等于区的数据而只处理两端分区数据，这样在大量重复场景下优化效果会非常明显。
三分区模式代码试验
代码测试了100w数据，数据是0-10的循环重复，测试耗时如下：
笔者使用相同的数据集在二分区模式下测试10w数据规模耗时大约是1800ms，数据集减少10倍耗时却增大了几十倍，或许二分区代码还是存在优化空间，不过这个对比可以看到存在大量重复元素时三分区性能还是很不错的。