6. 快速排序
# 快速排序
快速排序借用了分治的思想, 并且基于冒泡排序做了改进. 它由 C. A. R. Hoare 在 1962 年提出. 它将数组拆分为两个子数组, 其中一个子数组的所有元素都比另一个子数组的元素小, 然后对这两个子数组再重复进行上述操作, 直到数组不可拆分, 排序完成.
快速排序排序效率非常高. 虽然它运行最糟糕时将达到 O(n²)的时间复杂度, 但通常, 平均来看, 它的时间复杂为 O(nlogn), 比同样为 O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高. 之前在 捋一捋 JS 的数组 一文中就提到: Chrome 的 v8 引擎为了高效排序, 在排序数据超过了 10 条时, 便会采用快速排序. 对于 10 条及以下的数据采用的便是插入排序.
# 快速排序和归并排序的区别
快速排序先排序再递归细分，排序是从上到下的。
归并排序先递归细分再排序，排序是从下到上的。
# 稳定性
同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定
# 演示图
# 递归代码实现
var quickSort = function(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2); //基准位置（理论上可任意选取）
var pivot = arr.splice(pivotIndex, 1)[0]; //基准数
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right)); //链接左数组、基准数构成的数组、右数组
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 非递归实现
function quickSort(arr, left = 0, right = arr.length - 1) {
var list = [[left, right]]; // 模拟栈
while (list.length > 0) {
var now = list.pop();
if (now[0] >= now[1]) continue;
var i = now[0],
j = now[1],
flag = i;
while (i < j) {
while (arr[j] >= arr[flag] && j > flag) j--;
if (i >= j) break;
while (arr[i] <= arr[flag] && i < j) i++;
var temp = arr[flag];
arr[flag] = arr[j];
arr[j] = arr[i];
arr[i] = temp;
flag = i;
}
list.push([now[0], flag - 1]);
list.push([flag + 1, now[1]]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 快速排序的优化
优化思路：
- 合理选择 pivot
方案：（1）取中间值 （2）三点取中 （3）取平均值
你就直接选择分区的第一个或最后一个元素做 pivot 肯定是不合适的。对于已经排好序，或者接近排好序的情况，会进入最差情况，时间复杂度衰退到 O(N^2)。
pivot 选取的理想情况是：让分区中比 pivot 小的元素数量和比 pivot 大的元素数量差不多。
较常用的做法是三数取中（ midian of three ），即从第一项、最后一项、中间一项中取中位数作为 pivot。当然这并不能完全避免最差情况的发生。所以很多时候会采取更小心、更严谨的 pivot 选择方案（对于大数组特别重要）。比如先把大数组平均切分成左中右三个部分，每个部分用三数取中得到一个中位数，再从得到的三个中位数中找出中位数。
我在 javascript v8 引擎中看到了另外一种选择 pivot 的方式：认为超过 1000 项的数组是大数组，每隔 200 左右（不固定）选出一个元素，从这些元素中找出中位数，再加入首尾两个元素，从这个三个元素中找出中位数作为 pivot。
By the way，现实环境中，你要对一个预先有一定顺序的数组做排序的需求太太太普遍了，这个优化必须要有。
- 更快地分区
我看到题主的做法是从左向右依次与 pivot 比较，做交换，这样做其实效率并不高。举个简单的例子，一个数组 [2, 1, 3, 1, 3, 1, 3]，选第一个元素作为 pivot，如果按题主的方式，每次发现比 2 小的数会引起一次交换，一共三次。然而，直观来说，其实只要将第一个 3 和最后一个 1 交换就可以达到这三次交换的效果。所以更理想的分区方式是从两边向中间遍历的双向分区方式。
- 处理重复元素的问题
假如一个数组里的元素全部一样大（或者存在大量相同元素），会怎么样？这是一个边界 case，但是会令快速排序进入最差情况，因为不管怎么选 pivot，都会使分区结果一边很大一边很小。那怎么解决这个问题呢？还是修改分区过程，思路跟上面说的双向分区类似，但是会更复杂，我们需要小于 pivot、等于 pivot、大于 pivot 三个分区。既然说了不贴代码，那就点到为止吧，有兴趣可以自己找别人实现看看。
- 适时放弃快排
单次递归的数据量小于 16 时，我们改用插入排序
V8 引擎里调用 Array.prototype.sort()时，当数组长度大于 10 个的情况下，采用的是快速排序，而当长度小于等于 10 个时则切换为插入排序，以提高运算效率
参考：快速排序算法的优化思路总结 (opens new window)
# 三路快排
适用场景：当大量数据，且重复数多时，用三路快排
function qSort3(arr) {
// 三路快排
if (arr.length == 0) {
return [];
}
var left = [];
var center = [];
var right = [];
var pivot = arr[0]; // 偷懒，直接取第一个,实际取值情况 参考[快速排序算法的优化思路总结]
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else if (arr[i] == pivot) {
center.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...qSort3(left), ...center, ...qSort3(right)];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 单边递归法
单边递归则是每次只递归处理大的数据（或只处理小的数据）, 然后将小的数据代入下一次的分组过程中，也就是说第一次处理一半，第二次处理一半的一半。。。
单边递归法的递归次数为: 2 的 n 次方
假设每次取的基准恰好都将原数据分成了数量接近的两堆的递归次数为：2 的 n+1 次方 - 1
适用场景：需要注意的是，这种写法在可读性上略有不足，相比之下较难以理解，因此不适合在项目中使用，而是更多的出现在标准库中！
var partition = function(nums, star, ende) {
while (star < ende) {
let l = star,
r = ende;
let povit = getPovit(nums, l, r);
while (l <= r) {
while (l <= r && nums[l] < povit) l++;
while (l <= r && nums[r] > povit) r--;
if (l <= r) {
temp(nums[l], nums[r]);
l++;
r--;
}
}
partition(nums, l, ende);
ende = l;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18