给出十亿个数字，我们需要找到最大的一百万个数字

Question

我被困在一个问题中。

给出10亿个数字，我们需要找到最大的100万个数字。一种方法是对数字，然后从中获取O（n log n）中的前一百万个数字。提出一种算法预期的O（n）时间复杂度。

是具有O（n）复杂度的堆排序吗？

Answer 1

您要在此处解决的问题的一般版本如下：

给出n个数字，报告它们在（可能是预期的）时间O（n）中最大的k个。

如果只需要查找前k个元素，而排序无关紧要，则基于使用快速selection algorithms的问题，有一个聪明的O（n）时间算法。作为更新，选择算法将数组A和数字m作为输入，然后对数组A进行重新排序，以使m个最小元素在前m个时隙中，其余元素占据较大的时隙。 quickselect算法在（预期）时间O（m）内完成此操作，并且在实践中速度很快； median-of-medians算法在最坏的O（m）时间执行此操作，但在实践中较慢。虽然这些算法通常以找到smallest k个元素为框架，但它们与找到largest k个元素同样有效。

使用此算法作为子例程，这是我们如何找到时间和空间中前k个元素O（m）：

Initialize a buffer of 2k elements.
Copy the first k elements of the array into the buffer.

While there are elements remaining in the array:
    Copy the next k of them into the buffer.
    Use a selection algorithm to place the k largest elements
      of the buffer in the first k slots of the buffer.
    Discard the remaining elements of the buffer.

Return the contents of the buffer.
要了解其工作原理，请注意，在循环的每次迭代之后，我们保持不变，即缓冲区保存了到目前为止所见元素的k个最大元素（尽管不一定按排序顺序）。因此，该算法将识别输入的前k个元素，并以某种顺序返回它们。

就时间复杂度而言-创建缓冲区需要O（k）的工作，在循环的所有迭代中，我们进行O（n）的工作是将元素复制到缓冲区中。每次对选择算法的调用都占用（预期）时间O（k），并且对于算法的净运行时间为O（n + k），有O（n / k）个调用。在k

Answer 2

没有通用的排序算法可以在O（n）时间内完成此操作。此外，在没有其他约束的情况下（例如，从数字1到1,000,000取十亿个数字），根本没有适用于此的排序算法。

Answer 3

您可以通常