这叫做求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等人的《算法介绍》一书中也有非常详细的描述。

我想提出一个答案

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

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

干杯

遍历列表。如果当前值大于存储的最大值，则将其存储为最大值，并将1-4向下碰撞，5从列表中删除。如果不是，将它与第2条进行比较，然后做同样的事情。重复，检查所有5个存储值。应该是O(n)

Python中性感的快速选择

def quickselect(arr, k):
    '''
     k = 1 returns first element in ascending order.
     can be easily modified to return first element in descending order
    '''

    r = random.randrange(0, len(arr))

    a1 = [i for i in arr if i < arr[r]] '''partition'''
    a2 = [i for i in arr if i > arr[r]]

    if k <= len(a1):
        return quickselect(a1, k)
    elif k > len(arr)-len(a2):
        return quickselect(a2, k - (len(arr) - len(a2)))
    else:
        return arr[r]

转到这个链接的结尾:...........

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

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

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

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