结论
假设所有元素都是互异的，使用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)
预备知识：指示器随机变量
证明：
待补
