我想知道这是为什么 –费曼
快速排序从形式上为归分算法
1.分 核心是把数组按分界点一分为三
1
2
3
4
5
|
let pivot = array[array.length - 1]
let left = array.filter(
(item, index) => item <= pivot && index != array.length - 1
)
let right = array.filter((item, index) => item > pivot)
|
2.归 需要合并三个部分为一个数组
1
|
let result = [...left, pivot, ...right]
|
3.最后利用递归的思想，完成算法
递归步骤：
1.数组分为 3 部分，left pivot right，left<= pivot <right
2.递归处理左边的部分
3.递归处理右边的部分
4.合并三者的结果
1
2
3
4
5
6
7
8
|
function quickSort(array) {
let pivot = array[array.length - 1]
let left = array.filter(
(item, index) => item <= pivot && index != array.length - 1
)
let right = array.filter((item, index) => item > pivot)
return [...left, pivot, ...right]
}
|
递归是调用自身，不能无限次调用下去，因此需要有递归的出口（初始条件）
当数组元素长度小于 2 时，就已经是排好序了，不用再递归了，我们完善下代码
1
2
3
4
5
6
7
8
9
|
function quickSort(array) {
if (array.length < 2) return array
let pivot = array[array.length - 1]
let left = array.filter(
(item, index) => item <= pivot && index != array.length - 1
)
let right = array.filter((item, index) => item > pivot)
return [...qucikSort(left), pivot, ...quickSort(right)]
}
|
时间复杂度
我之前一直对时间复杂度的 log 感觉很模糊，看了下面这句话才恍然大悟
时间复杂度，2 的 64 次方个有序数据二分查找也顶多循环 64 次
此版本的快速排序每一次递归调用，需要额外空间，复杂度为 O(n)，不是本地排序。
说起空间复杂度，递归也需要空间（相当于手动维护一个调用栈），因此总体空间复杂度是 O(nlogn)。相等元素是不会交换前后顺序，因而是稳定排序（这与我们选择最后一个元素为分界点有关）。
时间复杂度为 O(nlogn)。
非常感谢老姚的文章：
手写算法并记住它：快速排序（5 行代码简单版）
