我想知道这是为什么 –费曼
在菜鸟算法第一篇中我们学习了简易版的快速排序，本篇介绍的是完整版的快速排序，马上你就知道简易版的有多屑！
相对于第五篇中的归并排序，快速排序完整版从原理是可以称为归分排序
具体过程：
选取最后一个元素为分界点，遍历数组每一次遍历都去找到小于等于分界点的元素再往数组前面交换
此时完成了将数组一分为三
因为是原地排序，所以不需要归并排序的合并操作
分
先按照具体过程写出《如何将数组一分为三》的代码
1
2
3
4
5
6
7
8
9
10
|
let array = [2, 4, 1, 9, 6, 3, 8, 5, 7]
let j = 0 //这是左边部分最后一位的index
let pivot = array[array.length - 1]
for (let i = 0; i < array.length; i++) {
if (array[i] <= pivot) {
;[array[j], array[i]] = [array[i], array[j]] //交换array[i] 到最前面
j++
}
}
console.log(array) //[2, 4, 1, 6, 3, 5, 7, 9, 8] 小于等于分界点所以分界点自己也交换位置到中间了
|
我们将其封装为函数
1
2
3
4
5
6
7
8
9
10
11
|
function partition(array, start, end) {
let j = start
let pivot = array[end]
for (let i = start; i <= pivot; i++) {
if (array[i] <= pivot) {
;[array[j], array[i]] = [array[i], array[j]]
j++
}
}
return j - 1 //减去for循环最后多加的一次，返回的是分界点交换到中间位置后的index
}
|
递归
回忆一下在简易版里的递归步骤： 1.将数组分为三部分 2.递归处理左边的部分 3.递归处理右边的部分
1
2
3
4
5
6
|
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 就不用递归了
即：
1
2
3
4
5
6
7
8
9
|
function quickSort(array, start = 0, end = array.length - 1) {
if (end - start < 2) {
return array
}
let pivotIndex = partition(array, start, end)
quickSort(array, start, pivotIndex - 1)
quickSort(array, pivotIndex + 1, end)
return array
}
|
复杂度
快速排序的时间复杂度平均是 O(nlogn)，在最坏的情况下，去排序一个已经排好序的数组，时间复杂度会提升至 O(n^2)
所以 partition 方法是可以优化的，常见策略有选中间、随机选、三选一等。假如这里我们随机选一个分区点，再与最后的元素交换，就能大概率避免最坏情形的出现。
1
2
3
4
|
//获取随机分界点
let randomIndex = Math.floor(Math.random() * (end - start + 1) + start)
swap(array, end, randomIndex)
let pivot = array[end]
|
由于是原地排序，所以没有空间复杂度，但是递归需要调用栈，所以总体的空间复杂度为 O(logn)，这里相较于简单版的快速排序的空间复杂度 O(nlogn)是有优化的
我创建了一个集合 jest 可以测试算法的靶场项目：
https://github.com/Llane00/algorithm-range-tests
将同步文章中的代码到这个项目下
使用 vscode 的读者可以安装拓展插件 jest，这个插件可以自动检测 test 文件自动运行，非常方便。
感谢老姚的文章 手写算法并记住它：快速排序（最易理解版）
