疾速排序
原文链接:https://note.noxussj.top/?source=sifo
什么是疾速排序(quickSort)?
次要分成两局部实现,分区、递归操作。
分区
从数组中任意抉择一个 “ 基准 ”,所有比基准小的元素放在基准后面,比基准大的元素放在根本前面。
递归
递归地对基准前后的子数组进行分区
算法步骤
- 首先获取数组的第一个值(作为基准)
- 遍历以后数组,从第二个值开始,比基准元素小的 push 到 left 数组,比基准元素大的 push 到 right 数组。
- 别离对 left 和 right 数组进行疾速排序(递归)
- 直到以后进行快排的数组长度为 1
- 开始合并,返回排列好的数组
- 实现排序
动画演示链接
https://visualgo.net/zh/sorting
示意图
根底案例
- 工夫复杂度:O (n * logn)
- 空间复杂度:O (1)
Array.prototype.quickSort = function () {const rec = (arr) => {if (arr.length <= 1) return arr
const mid = arr[0]
const left = []
const right = []
for (let i = 1; i < arr.length; i++) {if (arr[i] < mid) {left.push(arr[i])
} else {right.push(arr[i])
}
}
return [...rec(left), mid, ...rec(right)]
}
const res = rec(this)
res.forEach((n, i) => {this[i] = n
})
}
const arr = [5, 4, 3, 2, 1]
arr.quickSort() // [1, 2, 3, 4, 5]
上方代码中递归的复杂度是 O (logn),只有是波及到分成两半的都是 logn。分区操作的工夫复杂度为 O (n),因为循环遍历了 arr 数组。所以整体的工夫复杂度为 O (n * logn)。空间复杂度为 O (1),因为没有线性增长的变量。
原文链接:https://note.noxussj.top/?source=sifo