一篇文章让你真正了解快速排序

2次阅读

共计 2637 个字符，预计需要花费 7 分钟才能阅读完成。

只要是个工程师，就或多或少的知道快排，其中很多人都能轻松的写出一个快排的实现。但是大家了解阮一峰快排事件吗，是否知道快排的最佳实践？本文从一个争执讲起，通过生动详实的例子让你真正了解快排。嗯，这确实是一篇炒冷饭的文章，但我希望能把冷饭炒成好吃的蛋炒饭。闲话少叙，马上开始~
1. 阮一峰快排事件
整个事件用一句话来概括，就是有人 diss 阮一峰的快排写的不对，如下图。其实从图上也看到了，这个微博并没有发酵起来，直到一篇发表在掘金上的文章《阮一峰版快速排序完全是错的》（文章已经不能访问），然后又被人提问到知乎上，整个事情才变得热闹了起来。Diss 的主要点在于两个：

一个是拿哨兵用的 splice 而不是数组下标
一个是算法使用的是额外空间而不是原地分割

哨兵：快排中的被选中做为比较对象的基准元素

这件事情上，绝大多数同学都支持阮老师。其实，我觉得这种粗糙的批评是有问题的。有三个原因：
1.1 splice 已经被提及，并且时间复杂度没有量级上的区别
首先，在阮一峰的快排博客的评论里，他已经提到，splice 确实是有问题的，见下图。而且，即使使用了 splice，时间复杂度也是 O(n)+O(n)=O(n)，在量级上并没有影响。
1.2 算法没有规定空间复杂度，并且极端情况下的算法问题是通病
另外，快排在维基（中文 | 英文）的定义上只规定了时间复杂度，对于空间复杂度的定义是，
中文：根据实现的方式不同而不同英文：O(n) auxiliary (naive) O(log n) auxiliary

所以用空间复杂度来攻击算法是没有依据的。另外，winter 在上面知乎的问题中也提及，原地快排的空间复杂度因为不是尾递归必须用栈，空间复杂度是 O(log(n))，而即使快排每次都用新的空间，也无非是 O(2n)=O(n) 而已。
当然，若是极端情况下（哨兵每次都把数组分成 n - 1 和 1 个）阮老师的算法中空间复杂度会退化成 O(n 的平方)，不过这种情况是非原地快排的通病，而不是阮式算法的特例，所以也不能怪到阮老师头上。
1.3 基于通俗易懂的定位更值得肯定
阮老师的博客其实一直是通俗易懂的，我也把通俗易懂作为我自己一直的追求。这个算法可能不是没有瑕疵，但是却绝对称不上错。而我们做的也不是抨击瑕疵，而是考虑还有哪些改进的方向。
阮老师的这个快排实现确实好记，包括我自己，就是通过阮老师的这个算法才算真正记住了快排。在这个基础上，我觉得这个微博发的没啥意义。
2. 快速排序的复杂度分析
前面我们 BB 了半天阮一峰快排事件，中间我们多次提到了快排的时间复杂度和空间复杂度，在本部分，我们将分析为什么它们是这样的。

2.1 时间复杂度
如果足够理想，那我们期望每次都把数组都分成平均的两个部分，如果按照这样的理想情况分下去，我们最终能得到一个完全二叉树。如果排序 n 个数字，那么这个树的深度就是 log2n+1，如果我们将比较 n 个数的耗时设置为 T(n)，那我们可以得到如下的公式 [1]：
T(n) ≤ 2T(n/2) + n，T(1) = 0
T(n) ≤ 2(2T(n/4)+n/2) + n = 4T(n/4) + 2n
T(n) ≤ 4(2T(n/8)+n/4) + 2n = 8T(n/8) + 3n
……
T(n) ≤ nT(1) + (log2n)×n = O(nlogn)
而在最坏的情况下，这个树是一个完全的斜树，只有左半边或者右半边。这时候我们的比较次数就变为 =O(n 的平方)
2.2 空间复杂度
2.2.1 原地排序
原地快排的空间占用是递归造成的栈空间的使用，最好情况下是递归 log2n 次，所以空间复杂度为 O(log2n)，最坏情况下是递归 n - 1 次，所以空间复杂度是 O(n)。
2.2.2 非原地排序
对于非原地排序，每次递归都要声明一个总数为 n 的额外空间，所以空间复杂度变为原地排序的 n 倍，即最好情况下 O(nlog2n)，最差情况下 O(n 的平方)
对于复杂度这块还想了解更详细内容的同学可以参考《快速排序复杂度分析》
3. 快排的最佳实践呢
经过上面的部分，想必你对快排在前端的是是非非已经有了一个初步的了解。那么，什么是快排的最佳实践呢？
3.1 最简单好记
这是阮一峰老师的算法实现的变体，因为用了 es6 的写法，从而使得代码量变得更加精简，主体更加突出。
function quickSortRecursion (arr) {
if (!arr || arr.length < 2) return arr;
const pivot = arr.pop();
let left = arr.filter(item => item < pivot);
let right = arr.filter(item => item >= pivot);
return quickSortRecursion(left).concat([pivot], quickSortRecursion(right));
}
3.2 更高的效率
这里贴一个 winter 的实现，想看更多的实现，可以移步大佬们在 github 上的互喷地址
function wintercn_qsort(arr, start, end){
var midValue = arr[start];
var p1 = start, p2 = end;
while(p1 < p2) {
swap(arr, p1, p1 + 1);
while(compare(arr[p1], midValue) >= 0 && p1 < p2) {
swap(arr, p1, p2–);
}
p1 ++;
}
if(start < p1 – 1)
wintercn_qsort(arr, start, p1 – 1);
if(p1 < end)
wintercn_qsort(arr, p1, end);
}
3.3 实际情况下的优化方法
刚才也说到，快排其实是存在最差情况的。实际上，在日常工作中，如果真的有这样大数据量级的优化需要，我们往往会根据实际情况对快排进行各种各样的优化。
主要的思路有以下几点 [3]：