快速排序，简称快排。快排是所有排序算法中应用最广泛的。接下来我们将会说说一个经典的快排是如何实现的。
思路
快排的核心思想是分治。
所谓分治，就是分而治之的意思，将原来的问题拆分为多个规模较小子问题，这些子问题还能继续拆分，就是所谓套娃，直到规模小到直接求解。通过解决子问题，完成父问题，最终解决了原问题。
分治这个思想在实现上，使用的方法是递归。递归，是指函数执行中调用函数的一种形式，当递归到一定程度，就会触发退出递归的逻辑。
分治是思想，递归是方法，不要将二者混为一谈。
具体要做的就是对数组分区（partition） 。
对于提供的数组，我们随意从中找一个数组元素找出一个基准值（pivot），或者叫做中间值。然后通过分区函数（partition）将数组分为两部分，左边的小于等于 pivot 的部分，和右边的大于 pivot 的部分。
然后我们的分治（或者叫递归）就继续针对左侧和右侧进行同样的操作，直到区间大小小于等于 1。
实现
我们先看代码实现。
function quickSort(arr) {
partition(arr, 0, arr.length - 1);
return arr;
}
function partition(arr, lo, hi) {
if (lo >= hi) return; // 递归跳出条件，能够直接求解的子问题
const pivot = arr[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j) // 交换
i++;
}
}
swap(arr, i, hi);
partition(arr, lo, i - 1);
partition(arr, i + 1, hi);
}
function swap(arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
核心算法就是这个 partition 算法。该算法实现得很巧妙，能够做到原地排序（不使用额外的数据结构）。
partition 接受一个数组，以及要进行分区的索引区间 [lo, hi]，注意这是个左闭右闭的闭区间。
这里维护了一个 i 指针和一个 j 指针。j 指针每次迭代都会加一。[lo, i) 这个区间则代表小于等于 pivot 的区间，这个区间是动态的，因为 i 会变化。
在遍历时，如果当前值小于等于 pivot，就会把这个值放到 [lo, i) 区间。实现上就是交换 i 和 j 上数组元素的位置，然后让 i 自增一。
IMG_0501.jpg
需要特别注意的是，遍历是不能有 j == hi 的情况，并需要在遍历结束后将 pivot 请到中间。假设改为 j ≤ hi ，因为 i 对应的元素为大于等于 pivot 的元素，如果它比 pivot 大，i 和 pivot 就不会交换了。
为什么快排使用最广泛？
快排的平均时间复杂度是 O(n * logn)，比冒泡排序、插入排序这些时间复杂度为O(n^2)的算法要好得多。具体的推导过程有点复杂，这里就不进行展开了。
归并排序的时间复杂度同样是 O(n * logn)。快排在极端情况下，时间复杂度会退化变成 O(n^2)
，而归并排序不会。在时间复杂度上确实归并排序要更好一些。
但是快排能够做到原地排序，节省内存空间，即空间复杂度为 O(1)，而归并排序的空间复杂度为 O(n)。
但快排也有个严重的缺点，因为交换元素的关系，快排是不稳定排序。排序后，相同的值可能和原来相同值的相对顺序不同，只是排序数组还好，但在对对象根据 id 排序的情况时，可能就会让我们困扰。
一些奇怪的快排实现
在网上我看到这样的实现。
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));
};
这个实现思想上是对的，也是分治和分区思想，但致命问题是，它不是原地排序，需要用到额外的数组。面试的时候最好别写这种实现，虽然看起来更简短一些。
快排思想并不复杂，但实现上用了很多变量，对初学者还是需要花时间去理解。
本文首发于我的公众号：前端西瓜哥
网友评论