要点
算法思想与实现，优化思路，性能分析，三向切分，空间，优势
前言
快速排序之所以被称作“快速”，是因为快速排序是我们接触到的最快的通用排序算法，至于原因我们会在后面予以解释。鉴于快速排序的诸多优点，它成为应用最广泛的排序算法，具有优秀的性能，具体我们会在后面进行分析。
相对于初级排序算法、归并排序等，快速排序显现出了它的脆弱性，我们需要在实现时非常小心，才能避免隐藏在深处的性能漏洞。这就像爬山一样，你可以选择走缓慢的、没有风险的缓路，也可以选择可以快速登顶的险路，这样便需要承担风险的代价，但是这会促使我们不断磨炼登山的技巧。同样的道理，快速排序中遇到的性能漏洞会使我们不断改进快速排序算法，让它的使用范围更加广泛。
算法思想
快速排序利用了分治的思想，将一个待排序的数组分为两个较小的子数组，再将两个子数组独立排序。
我们先在待排序的数组中选择（如何选择？下面讲）一个元素a作为基准元素，从数组的头部和尾部开始遍历数组，从头部找到第一个比a大的元素b和从尾部找到第一个比a小的元素c，将b和c的位置互换，重复这样的工作直到头部和尾部的指针相遇，这样原数组就被a切分成了小于a（左部）和大于a（右部）两个部分，再进一步将两个子数组用相同的方式切分只到数组只有一个元素，达到分而治之的目标。
切分后的a的位置应该就是最终排序结果中a应该处于的最终位置，因为不管它左部（或右部）的元素是否已经排序，小于a（大于a）元素的个数是不变的。
算法实现
根据上述的思路，我们可以写出我们的伪代码
- 获取待排序数组
- 从数组选出一个元素作为基准
- 将数组按照左右遍历并相互交换的方式切分为两个子数组A, B
- 将数组A排序
- 将数组B排序
根据伪代码写出排序代码
/*
* 快速排序的驱动函数
*/
public static void sort(char[] src)
{
int n = src.length;
sort(src, 0, n - 1);
}
/*
* 递归调用
* lo, hi用于跟踪递归进度
*/
public static void sort(char[] src, int lo, int hi)
{
if (lo >= hi)
return ;
int splitIndex = partition(src, lo, hi); //切分
sort(src, lo, splitIndex - 1);
sort(src, splitIndex + 1, hi);
}
接下来便是快速排序的核心部分partition函数，它的目的是将数组按照上述讨论的方式对数组调整、切分并返回切分元素最终的位置
/*
* 快速排序的核心
* 用段落的第一个元素作为切分的标准
* 将小于它的都放在左部分，大于它的都放在右部分
* 从左到右找大的，从右到左找小的，做交换
* 最后找到最靠右的小于标准元素的元素与标准元素进行交换
*/
public static int partition(char[] src, int lo, int hi)
{
int base = src[lo];
int l = lo, h = hi + 1;
while (true)
{
while (src[++l] < base)
if (l == hi)
break;
while (src[--h] > base)
if (h == lo)
break;
if (l < h)
exchange(src, l, h);
else
break;
}
/*
* 这里的h换成l-1都可以，表示左侧部分最右的一个元素
*/
exchange(src, lo, h);
return h;
}
这里exchange方法表示交换数组指定下标的两个元素的位置。
这是最基础的实现方式，所以我们只是简单地图方便地选择了数组的第一元素作为基准元素，后续我们会看到更多的选择方式。
在这里，左右指针扫描的时候检测的时候采用的是遇到相等的元素的时候停止扫描而不是跳过（例：<和<=的区别），这样做可以让等值的元素更接近于最终位置，目的是避免算法在遇到大量重复元素时运行时间变成平方级别（虽然会有不必要的等值元素的交换）。
下面我们会通过跟踪排序过程的方式帮助大家理解快速排序算法
其中粗体元素表示切分元素，用“[”和“]”表示切分的子数组的边界。
性能
快速排序的核心是切分函数，其算法的性能关键决定因素也是切分的效果
如果每次切分都可以将数组分成等长的两个子数组分别处理，切分效果应该是最佳的，这类似于二分法。我们用C来表示比较的成本
CN= C左 + C右 + N=2CN/2 + N
解递推公式得，这种情况的成本~NlgN
最差的结果应该是每次切分都有一个子数组为
空，显然这种情况的成本~N2
平均情况的性能
书中给出了两个命题，证明过程有兴趣的朋友可以细读书中说明
在长度为N的无重复数组排序，快速排序平均需要~2NlnN次比较（以及1/6的交换）
在这里，2NlnN约等于1.39NlgN，所以平均情况的比较次数比排序算法最好情况多出39%
快速排序最多需要约为N2/2次比较，但随机打乱数组能够预防这种情况
这种情况在小数组出现的概率相对大一些，随着N的增大，运行时间会逐渐接近平均情况，出现平方级别的概率越来越小。
书中举了个例子，对于一个有100万个元素的数组，快速排序运行时间是平均情况所需时间10倍的概率小于0.00001，所以达到平方级别的概率更会小很多，这需要概率知识中的Chebyshev不等式的支持。所以我们完全可以说随机打乱可以预防出现平方级别的情况。
算法优化
我们在算法优化的过程中可以尝试很多种方式，我们可以使用一个辅助数组让切分的实现更加容易，但是复制数组的开销以及辅助数组的空间代价会使我们很容易放弃这个想法（失去了相对于归并排序不需要辅助空间的优势）。下面的几种方式是有效的
随机预处理
刚刚我们说到选择基准元素的方式是选择第一个元素，这是最简单的，也是性能最差的，因为这对于输入很敏感，对于特殊性的输入会有非常差的性能。我们可以在排序之前将所有元素顺序随机打乱，对每个元素平等对待，这时再选择第一个元素相当于是待排序数组中的一个随机元素。在之前的性能分析中，我们了解到这种随机化处理很有必要。
/*
* 优化1
* 加入随机性
*/
public static void sort(char[] src)
{
int n = src.length;
shuffle(src);
sort(src, 0, n - 1);
}
shuffle方法表示随机打乱数组元素顺序
去掉边界测试
细心的朋友可以发现，基础实现中的左端边界测试条件（h == lo）是多余的，因为一个元素a[lo]不可能比自己还小，通过这里得到灵感，我们同样可以去掉右端的边界测试条件，在随机打乱数组的时候将最大值移动到数组末尾作为哨兵，如果指针指向的元素小于base进入循环，那它一定不是在数组末尾，因为末尾的元素是最大值，这样就起到了哨兵的作用，免去边界条件测试。
结合插入排序
我们知道，插入排序对于有很少乱序元素的待排序数组来说是最快的，因为它仅仅对于元素进行必要的比较和在需要的地方进行元素移动，接近线性级别。
快速排序在即将排序成功的时候，对于较小的数组我们仍需要对其进行切分、递归调用，我们采取的措施显得有点大材小用了，基于插入排序的优势，我们可以在数组大小小于阈值M的时候采用插入排序，完成排序的最后一步，这会有效的提升算法效率，阈值可以根据不同场景进行调整。
/*
* 优化3
* 加入插入排序
*/
public static void sort(char[] src, int lo, int hi)
{
if (lo + M>= hi)
{
insertSort(src, lo, hi);
return ;
}
int splitIndex = partition(src, lo, hi);
log(src, lo, hi, splitIndex);
sort(src, lo, splitIndex - 1);
sort(src, splitIndex + 1, hi);
}
其中M为阈值，insertSort方法利用插入排序将指定的数组排序
三取样切分
这是另一种选择切分元素的方式，比之前的随机化处理后选择第一个元素更合理，我们可以选择待排序数组中的一小部分元素的中位数来切分数组，但是要付出找中位数的代价。所以我们常选用三取样切分的方式，我们从数组中随机取得三个元素选择它们中的中位数作为基准元素，这样做还有一个好处，取样元素还可以作为哨兵放在尾部，免去边界测试。
随机三次取样的代价较大，我们可以最开始随机打乱数组，并指定第一个、最后一个和处于中间位置的元素中的中位数作为基准元素。有的地方把这种方法称为三数取中法。
三向切分的快速排序
在实际应用中，我们很少会处理无重复元素的数组，经常会遇到含有大量重复元素的数组，而我们之前的基础排序算法对于重复的元素仍对其进行比较和大量的交换，这显然是没有必要的，在其中我们便可以发现巨大的优化潜力，在特定的情况下将线性对数级别的性能进一步改进。
三向切分的思路
之前的算法是将数组分为两个部分，小于基准元素和大于基准元素，三向切分将数组分为三个部分：小于、等于和大于基准元素。所以我们需要更多的指针跟踪（lo, lt, i, gt, hi），我们让a[ lo ... lt - 1 ]存储小于基准元素的元素，a[ lt ... i - 1]存储等于基准元素的元素，a[ i ... gt ]存储未访问到、未确定大小的元素，a[ gt + 1 ... hi ]存储大于基准元素的元素。
实现
基于上面对于指针的要求，我们写出下面三向切分的代码
/*
* 这里是和普通快速排序不一样的地方
* 这里维护几个索引
* 用i跟踪当前待比较的那一个元素
* 通过不断地递归将数组切分成三个部分
* src[lo...lt-1]：小于部分
* src[lt...gt]：等于部分
* src[gt+1, hi]：大于部分
*/
public static void sort(char[] src, int lo, int hi)
{
if (lo >= hi)
return ;
int lt = lo, gt = hi, i = lt + 1;
char base = src[lo];
while (i <= gt)
{
/*
* 对三种情况的处理
*/
if (src[i] < base)
exchange(src, lt++, i++);
else if (src[i] > base)
exchange(src, gt--, i);
else
i++;
}
sort(src, lo, lt - 1);
sort(src, gt + 1, hi);
}
- 当前元素小于基准元素：lt-1是小于部分的最右元素，i-1是等于部分的最右元素，小于部分需要增加一个元素，所以lt和i均加一。
- 当前元素大于基准元素：gt+1是大于部分的最左元素，大于部分需要增加一个元素，所以gt减一。
- 当前元素等于基准元素：i-1是等于部分的最右元素，等于部分需要增加一个元素，所以i加一。
下面我们通过跟踪排序过程的方式加深对于三向切分快速排序的理解
其中粗体字符表示当前迭代相对于上一次的变化点。
优化原理
其实我们也可以把和基准元素相等的元素看成一个整体，每一次切分都会将与基准元素相等的元素排好。避免了在一次迭代后大量重复的元素会零散地分布在基准元素左部和右部的情况。递归的边界变为数组头部到重复元素集合的左部（lo到lt-1）和重复元素集合右部到数组末尾（gt+1到hi），而不是只关注基本元素这一个元素，减少递归次数，极大地提高效率。
性能分析
三向切分排序在面对只有若干个不同主键的随机时，时间复杂度可以达到数组长度的线性倍数级别。
有的朋友会有疑问，归并排序的~NlgN次比较不应该是最优的时间复杂度吗？这是因为归并排序中的最优讨论的是在任何输入下的最差性能，而三向切分关注的是含有大量重复元素的输入情况，也就是我们已经知道了输入的一些特性，所以对于这种情况，归并排序无法达到最佳。
信息熵
上面所说的一个含有重复数组的重复情况如何，如何量化，以便于我们研究三向切分的性能？我们需要熟悉一下信息熵的概念，信息熵表示所含信息量的大小，这与其中每个元素的概率相关。我们用k表示数组中主键的个数，用pi表示第i个主键在一次随机抽取行为中出现的概率，则我们待排序数组的信息熵为
所以信息熵的大小，也是信息量的大小，由元素的概率分布情况影响。通过计算信息熵，我们可以得出三项切分比较次数的结论，见书中命题
对于大小为N的数组，三向切分的快速排序需要~(2ln2)NH次比较。其中H为由主键值出现频率定义的香农信息量。
基于信息熵的意义，当数组中所有元素都不重复时其所包含的信息量最大，信息熵的值最大，所以三向切分快速排序的最差情况是所有元素均不重复，即p1= p2 = ··· = pk = 1 / N，H = lgN，此时~(2ln2)NH = ~1.39NlgN，回到了之前命题的结论。
其实这种情况也只比归并排序多出39%，只要重复的元素稍多便会在性能上好于归并排序，而在实际应用中，存在大量重复元素的例子非常常见。
空间
快速排序采用的是原地排序，不需要辅助空间，它的递归性决定了它需要递归深度等量的栈空间，所以空间复杂度在logN在N之间。
为了减少递归深度，可以递归排序两个子表中较小的，再用循环代替第二个递归，这样能让我们的递归深度最多是logN，这样当然对于时间复杂度不友好，但是我们在一些对于栈空间有严格要求的场景不妨使用这种方法。
快速排序的优势
相对于那些初级排序算法（插入排序、选择排序等），快速排序的优势不用多说，平均情况的线性对数级别比平方级别在性能上要好太多。而最差情况的平方级别完全可以通过随机化避免。
相对于归并排序。在空间上，归并排序的劣势显露无疑，归并排序需要线性级别的空间，所以只需要对数级别的空间。在时间上，上面已经进行了详细讨论，三向切分快速排序在实际应用中的性能优于归并排序很多。
相对于堆排序。堆排序在时间和空间上都有非常好的效果，但是它总是跳跃式地访问元素，无法利用缓存，而快速排序总会顺序地访问元素，可以利用缓存。而缓存对于性能的提升是非常有用的。
快速排序的内循环中的指令很少，运行时间的增长数量级为~cNlgN，并且三向切分的快速排序对于实际应用中可能出现的某些分布的输入变成了线性级别，这使得其他的排序算法望而却步。
所以，我们会说快速排序是最快的通用排序算法，而三向切分的快速排序也成为了排序库函数的最佳算法选择。也如书中所说
我们需要在运行时间至关重要的任何排序应用中认真地考虑使用快速排序
结束语
文章参考
- 《算法（第4版）》——Robert Sedgewick & Kevin Wayne 著
- 《算法设计与分析（第3版）》——王晓东 著
- 《数据结构（C++描述）》——金远平 著
并结合本人自身的理解，希望对大家有所帮助，有不足之处望朋友们指出，欢迎大家积极评论，遇到问题一起讨论，谢谢！
