对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？
本系列文章就尝试解决这个问题。
研读那些排序算法，细品它们的名字，其实都很贴切。
比如快速排序，一个快字就能体现出其价值，因而它是用得最多的。
因为它相对难一些，本系列将分两篇文章讲解它。
快速排序这个名字是针对其性能来起的，但很难让人做到见名知意。
所以，给它重新起了个名字：归分排序。
与归并算法一样，归分算法也是分而治之算法，讲究分、归、并。归并的重头戏在于如何去合并，快排的重头戏在于如何去划分。
上图中，先把数组按最后一个元素4作为分界点，把数组一分为三。除了分界点之外，左子部分全是小于等于4的，右子部分全是大于4的，它们可以进一步递归排序。因为是原地排序（不需要额外空间），因此不需归并那种合并操作。
其中，归相对容易些，该算法的核心是：如何把数组按分界点一分为三？
各个教程的实现方式不一，这里我介绍一个最容易理解的方式。
具体过程是这样的，选取最后一个元素为分界点，然后遍历数组找小于等于分界点的元素，然后往数组前面交换。比如：
上图中，我们按顺序找小于等于4的元素，共1、2、3、4。然后分别与数组的前4个元素交换即可，结果自然是一分为三。
是不是非常容易理解的思路？快排也不难学嘛。
我们用JS实现一遍：
let array = [7, 1, 6, 5, 3, 2, 4]
let j = 0
let pivot = array[array.length - 1]
for (let i = 0; i < array.length; i++) {
if (array[i] <= pivot) {
swap(array, i, j++)
}
}
console.log(array) // [ 1, 3, 2, 4, 7, 6, 5 ]
其中swap函数封装了两个元素如何交换：
function swap(array, i, j) {
[array[i], array[j]] = [array[j], array[i]]
}
进一步封装成函数：
function partition(array, start, end) {
let j = start
let pivot = array[end]
for (let i = start; i <= end; i++) {
if (array[i] <= pivot) {
swap(array, i, j++)
}
}
return j - 1
}
start和end表示数组起止下标。最后返回的j-1是分界点的位置。
接下来就需要递归处理左子部分和右子部分了。
对于递归，虽然它不符合线性思维，但其实也没啥难的。
只要有递归步骤（递归公式），很容翻译成代码的。
我们再回忆一下快排算法的步骤：
- 数组分成三部分left、pivot、right，使left<=pivot，right>pivot。
- 递归处理left
- 递归处理right
轻松翻译成代码：
function quickSort(array, start = 0, end = array.length -1) {
let pivotIndex = partition(array, start, end)
quickSort(array, start, pivotIndex - 1)
quickSort(array, pivotIndex + 1, end)
return array
}
递归是自身调用自身，不能无限次的调用下去，因此需要有递归出口（初始条件）。
它的递归出口是，当数组元素个数为小于2时，就是已经是排好序的，不需要再递归调用了。
因此需要在前面加入代码：
if (end - start < 1) return array
至此，快速排序原理和实现已经说完了。
快排的算法主要在于partition函数的实现，不同教程的实现方式都不一样，这个需要注意一下。
其时间复杂度平均是O(nlogn)。最坏情形是，假如待排的数组已经是排好序的，该算法将退化成O(n^2)级的。此时可以通过合理的分区点选择来避免。常见策略有选中间、随机选、三选一等。假如这里我们随机选一个分区点，再与最后的元素交换，就能大概率避免最坏情形的出现。完整代码：
const utils = {
swap(array, a, b) {
[array[a], array[b]] = [array[b], array[a]]
},
randomNum() {
return Math.floor(Math.random() * 100)
},
randomArray() {
return Array.from(Array(this.randomNum()), _ => this.randomNum())
}
}
function partition(array, start, end) {
let j = start
let pivot = array[end]
for (let i = start; i <= end; i++) {
if (array[i] <= pivot) {
utils.swap(array, i, j++)
}
}
return j - 1
}
function quickSort(array, start = 0, end = array.length -1) {
if (end - start < 1) return array
let pivotIndex = partition(array, start, end)
quickSort(array, start, pivotIndex - 1)
quickSort(array, pivotIndex + 1, end)
return array
}
let array = utils.randomArray()
console.log(quickSort(array))
这里总结一下，快速排序是原地算法，不需要额外空间，但递归是需要空间的的（相当于手动维护个调用栈），总体空间复杂度是O(logn)。相等元素可能会交换前后顺序，因而不是稳定排序（因为交换）。时间复杂度为O(nlogn)。
快速排序，要做到能分分钟手写出来，是需要掌握其排序原理的。关键在于，如何按照分界点把数组一分为三。至于递归，只要能说清楚递归步骤和出口，就能很容易写出来，不需要死记硬背的。
希望有所帮助，本文完。
