这叫做求k阶统计量。有一个非常简单的随机算法(叫做quickselect)，平均时间为O(n)，最坏情况时间为O(n²)，还有一个相当复杂的非随机算法(叫做introselect)，最坏情况时间为O(n)。维基百科上有一些信息，但不是很好。

你需要的一切都在这些幻灯片里。只需提取O(n)最坏情况算法(introselect)的基本算法:

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    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等人的《算法介绍》一书中也有非常详细的描述。

你可以用O(n + kn) = O(n)(对于常数k)表示时间，用O(k)表示空间，通过跟踪你见过的最大的k个元素。

对于数组中的每个元素，您可以扫描k个最大的元素列表，并将最小的元素替换为更大的新元素。

Warren的优先级堆解决方案更简洁。

我提出了这个算法，似乎是O(n):

假设k=3我们想找出数组中第三大的元素。我将创建三个变量，并将数组中的每一项与这三个变量中的最小值进行比较。如果数组item大于最小值，则用item的值替换最小值变量。我们继续做同样的事情，直到数组结束。三个变量中的最小值是数组中第三大的项。

define variables a=0, b=0, c=0
iterate through the array items
    find minimum a,b,c
    if item > min then replace the min variable with item value
    continue until end of array
the minimum of a,b,c is our answer

为了找到第K大的项，我们需要K个变量。

例如:(k = 3)

[1,2,4,1,7,3,9,5,6,2,9,8]

Final variable values:

a=7 (answer)
b=8
c=9

有人可以审查这个，让我知道我错过了什么?

下面是完整实现的链接，其中相当广泛地解释了在无序算法中查找第k个元素的算法是如何工作的。基本思想是像快速排序一样对数组进行分区。但为了避免极端情况(例如每一步都选择最小的元素作为主元，使算法运行时间退化为O(n^2))，采用特殊的主元选择，称为中位数的中位数算法。在最坏情况和平均情况下，整个解在O(n)时间内运行。

这里是全文的链接(它是关于寻找第k个最小的元素，但寻找第k个最大的元素的原理是相同的):

在无序数组中寻找第k个最小元素

我想提出一个答案

如果我们取前k个元素并将它们排序成一个k个值的链表

对于每一个其他的值，即使在最坏的情况下如果我们对剩下的n-k个值进行插入排序即使在最坏的情况下，比较的数量也将是k*(n-k)对于前k个要排序的值让它是k*(k-1)所以结果是(nk-k)也就是o(n)

干杯

我实现了在n个未排序元素中寻找第k个最小值的动态规划，特别是竞赛方法。执行时间为O(n + klog(n))。所使用的机制在维基百科关于选择算法的页面上被列为方法之一(如上面的帖子之一所示)。你可以阅读算法，也可以在我的博客页面“查找k个最小值”上找到代码(java)。此外，逻辑可以对列表进行部分排序——在O(klog(n))时间内返回第一个K min(或max)。

虽然代码提供了第k个最小值的结果，但可以使用类似的逻辑来查找O(klog(n))中的第k个最大值，忽略创建比赛树的前期工作。