TOC
选择算法
所谓的选择算法，其基本规则就是从一个无序的数组中，找到第 i 小的值。 最简单的做法其实就是将数组排序，下标+1 就是它的 i。但是，就算依托于随机快排，也依然需要 O(nlogn)的时间，那么，有没有一种方法可以再线性时间，也就是 O(n)内完成查找呢？
// 获得一个n到m的随机数
function rd(n, m) {
var c = m - n + 1
return Math.floor(Math.random() * c + n)
}
function randomSelect(arr, i) {
if (arr.length <= 1) {
return arr[0]
}
let pivotIndex = rd(0, arr.length - 1)
let pivot = arr.splice(pivotIndex, 1)[0]
let left = []
let right = []
for (let i = 0; i < arr.length; i++) {
let cur = arr[i]
if (cur < pivot) {
left.push(cur)
} else {
right.push(cur)
}
}
// p就是当前第p小的值 如果p===i则代表正好符合要求
let p = left.length + 1
if (p === i) {
return pivot
}
// 递归继续查找
if (i < p) {
return randomSelect(left, i)
}
if (i > p) {
// 注意 如果是选择右边递归，其第i小本身的基础会被砍 需要减去砍的部分
return randomSelect(right, i - p)
}
}
其实这个算法和快排几乎一致，其核心变化在于本来分成两个子树的结构变成了分成一个子树，并且瞬间减少了一般的计算量。它再绝大多数情况下都能符合Ω(n)的时间，其最差情况 = O(n^2)