这称为查找第 k阶统计量 。有一个非常简单的随机算法（称为 quickselect
），它占用了
O(n)平均时间，
O(n^2)最坏情况下的时间，还有一个相当复杂的非随机算法（称为 introselect
），它占用了
O(n)最坏情况的时间。在Wikipedia上有一些信息，但这不是很好。
您需要的所有内容都在。仅提取
这些PowerPoint幻灯片中
O(n)最坏情况算法的基本算法（introselect）：
Select(A,n,i): Divide input into ⌈n/5⌉ groups of size 5. medians = array of each group’s median. pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉) Left Array L and Right Array G = partition(A, pivot) k = |L| + 1 If i = k, return pivot If i < k, return Select(L, k-1, i) If i > k, return Select(G, n-k, i-k)
在Cormen等人的《算法介绍》一书中，它也做了非常详细的介绍。
