如何在O（n）中长度为n的未排序数组中找到第k个最大元素？

如何在O（n）中长度为n的未排序数组中找到第k个最大元素？

这称为查找第 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等人的《算法介绍》一书中，它也做了非常详细的介绍。