从大量整数中选取最小 / 大的若干个

方法一：快速选择 / 线性选择算法

快速选择和线性选择算法都是平均时间复杂度 O(n) 的选择算法，当然线性选择算法在最坏情况下也能保证 O(n) 时间，缺点是实现起来比较复杂。简单起见，我就用快速选择算法。

快速选择算法类似于快速排序，用一个轴值将数组分成两部分，一部分全都比轴值小，而另一部分全都比轴值大。然后看看两部分分别包含多少个元素，从而确定第 m 大的元素应该再哪一半，然后对那一半递归处理，直到找到第 m 大的元素。

但是将快速选择算法应用到本题时，遇到主要问题是内存恐怕不够。

如果在内存中放入所有的对象，我们需要 12G 到 120G 内存，取决于对象的个数是十亿还是一百亿。进入内存后，还需要至少两次遍历才可以找到第 m 大的元素。另外加载数据时需要有一次完整的文件遍历。

如果内存中无法放入所有的对象，那就比较麻烦了，在头几次二分递归的时候可能需要动用硬盘来缓存数据，磁盘 IO 将成为可怕的瓶颈。累加起来相当于至少两次全文件的读遍历和写遍历。实际上，在确定了第 m 大的对象后，可能还需要遍历一次整个文件，找出比它小的对象。

方法二：堆排序算法

堆排序也是一个很好的可以用于部分排序的算法，C++ STL 就用堆排序来实现 partial_sort。

在内存中维护一个大小为 m 的最大值堆（没错，是最大值堆），遍历整个文件，每拿到一个对象，拿它与堆顶的属性值比较一下，如果新对象的属性值大就直接丢弃，否则用它取代堆顶元素。平均来讲，这样处理的时间复杂度是 n * log m。

方法三：哈希算法

我们注意到，虽然对象的个数非常大，但属性值的范围非常小（相对来讲）。如果在值域范围上建立一个哈希表，只需要 100M 个格子，如果一个格子存储一个 32 位整数，只需要 400M 内存。

哈希表总是会有冲突的，在这个问题中，冲突是必然的，平均每个属性值上会有 10 到 100 个不同的对象。但处理冲突的办法非常简单，因为我们不需要在哈希表中记录每个对象，只需要记录这个属性值对应的对象的个数。

开辟一个能存放 100M 个 32 位整数的数组（为保险起见，可以用 64 位整数，但总共也只需要 800M 内存），数组的下标对应于属性值（实际操作中可能要减一）。然后遍历整个文件，每拿到一个对象，将对应的数组元素值加一。

文件遍历完后，过一下这个数组，可以找出第 m 大的对象的属性值，这个值就是一个边界。然后再遍历一次原始文件，把属性值小于等于边界的对象都放到内存中（注意在相等时，会有个数的限制）。最后把内存中的 m 个对象按照属性值排一下序再输出即可。

这样最多只需要遍历两次文件，使用 O(n) 时间就可以完成题目的要求。

到底哪个方法快？

上面提到了三种算法，到底哪一个最快呢？说说你的看法吧？

我以前一直觉得哈希法是最快的，它对内存的需求量适中，算法是线性时间。但后来又仔细想了想，觉得不太对。这里实际上不完全是内存中的运算了，瓶颈主要是在磁盘 IO 上。

让我们来比较一下三种算法：

1. 快速选择算法（所有对象可以全进内存）：只需要一次文件读遍历，内存操作是 O(n) 时间（系数至少为 2，可能会很大）。
2. 快速选择算法（只有部分对象可进内存）：平均需要三次文件读遍历，两次写遍历，内存操作是 O(n) 时间（系数至少为 2，可能会很大）。
3. 堆排序算法：需要一次文件读遍历，内存操作是 O(n * log m) 时间，这里 m 取 10000 的话，大概是 13。当然实际数值会少于 13，因为并不是每个对象都需要进入堆中。
4. 哈希算法（所有对象可以全进内存）：需要一次文件读遍历，在内存中要开辟大小为 O(n) 和 O(m) 的两块缓冲区，内存操作时间为 O(n)（系数大约为 2）。
5. 哈希算法（只有部分对象可进内存）：需要两次文件读遍历，内存操作是 O(n) 时间（系数小于 2）。

题目的本意就是几乎不可能让所有对象都进入内存。虽然堆排序的内存操作时间复杂度偏高，却只需要一次磁盘遍历操作，其消耗的时间应该要小于哈希算法的。你是否同意呢？

最近做了个实验，生成了十亿个对象，每个对象有一个 64 位整数作为标识符，还有一个不超过一亿的随机整数作为属性值。生成的文件用文本格式存储，占用 18G 磁盘空间。我没有实验快速选择算法，只是比较了堆排序和哈希。实验结果是：

• 单纯遍历一次文件，包括逐行读取，把属性值解析成整数：耗时 34 分钟；
• 堆排序算法：耗时 40 分钟；
• 哈希算法：耗时 73 分钟。

这三个时间的相对值是否在你的预料之中呢？

当然，如果把硬盘换成 SSD 恐怕结果又完全不同了，有兴趣的童鞋可以试一试。