算法-寻找顺序统计量

结论

假设所有元素都是互异的，使用RANDOMIZED-SELECT算法可在期望为线性时间内找到任一顺序统计量，特别是中位数。

RANDOMIZED-SELECT算法

RANDOMIZED-SELECT(A, p, r, i)
  if  p == r
      return A[p]
  q = RANDOMIZED-PARTION(A, p, r)
  k = q - p +1
  if i == k
    return A[q]
  else if i < k
    return RANDOMIZED-SELECT(A, p, q-1, i)
  else 
    return RANDOMIZED-SELECT(A, q+1, r, i-k)

预备知识：指示器随机变量
证明：
待补