海量数据中选出若干大数字的算法

今天去面试了一家公司，被问到了这样一道题目：
如何最快的从1M数据中选出100个最大的数据。

问题不在于找出最大的数据，而是在于最快的算法。

我们可以建堆来搞定这件事，比如建一个100的小顶堆。这样只需要和最小的比较就好了。
这个大概时间复杂度为O(n log^2 m) 应该说这是一个比较不错的方案。

也许还有更快的方案。

比如快速排序。
如果我们快速排序支点选择的好，可以加速这个寻找的过程。
比如说，如果我们很幸运，找到了第m+1个大的数目，基本一次快排就搞定了。

所以下面的问题就是我们通常没那么走运，那么如何选择支点就是一个可以优化的方向。
如何选择支点呢？
一个简单的方法，经过一次扫描，得到数据中最大值和最小值，然后二分来做为支点。
这样由于二分其实是一个很不错的降解方案（不用考虑数据分布了）。可以很快找到m个数字。

所以应该在数据规模不是很大的情况下，应该用二分+快排来搞定这件事情。
当然如果规模更大的话就要考虑桶排序或者bitmap之类的啦。

另外，这种题目基本不是来考验人的应变的，更多的感觉是考验一个人的经验。