选择算法

所谓的选择算法,其基本规则就是从一个无序的数组中,找到第 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)