在不排序的情况下找出无序列表的第N项

Question

你好。我有一个非常大的数组，我想找出第N个最大的值。简单来说，我可以先把这个数组排序，然后取出第N个元素，但因为我只对一个元素感兴趣，所以可能有比排序整个数组更好的方法……

Answer 1

一种简单的改进版快速排序在实际应用中效果很好。它的平均运行时间和数据量N成正比（不过在最坏的情况下，可能会遇到O(N^2)的糟糕运行时间）。

操作方式和快速排序类似。首先随机选择一个基准值，然后遍历你的数据，看看每个值是高于还是低于这个基准值，然后根据这个比较把它们放进两个箱子里。在快速排序中，你会递归地对这两个箱子进行排序。但在计算第N个最大值时，你只需要对其中一个箱子进行排序。每个箱子里的数据量可以告诉你哪个箱子里有你要找的第N个最大值。举个例子，如果你想找第125个最大值，而你把数据分成了两个箱子，其中“高”箱子有75个值，“低”箱子有150个值，那么你可以忽略“高”箱子，直接去找“低”箱子里的第125-75=50个最大值。

Answer 2

堆是一种非常适合这个操作的数据结构，而Python有一个很棒的内置库可以用来处理堆，叫做heapq。

import heapq

def nth_largest(n, iter):
    return heapq.nlargest(n, iter)[-1]

使用示例：

>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920

通过排序来确认结果：

>>> list(sorted(iter))[-10]
920

Answer 3

排序至少需要 O(nlogn) 的运行时间，这个时间复杂度是比较高的。不过，有一些非常高效的 选择算法 可以在更短的时间内解决你的问题，达到线性时间的效果。

基于分区的选择（有时候叫 快速选择）是基于快速排序的思想（通过递归分区来实现），这是一个不错的解决方案（可以查看链接获取伪代码 + 另一个例子）。