编程之美2.5——寻找最大的K个数

问题：

从一组数中选出其中最大的K个数，当这组数的个数为几百、几百万、几百亿时分别适合采用哪些算法？

个数为几百时，使用顺序统计法（看算法导论第9章）：

算法思想是对输入数组进行递归划分，一边的数据小于选定数，另一边的数据大于等于选定数。但和快速排序不同的是，快速排序会递归处理划分的两边，而顺序统计法只处理划分的一边。其随机化算法的期望时间为O(n)。

个数为几百万时，数据量较大不适合全装入内存中，能容忍多次访问，可使用二分中值法（用法有点奇怪，个人不太喜欢）：

本质上是通过二分思想找出第K大的数的值。算法从[Min, Max]开始逐渐缩小第K大的数取值的范围，时间复杂度为O(N*log(Max-Min))。

个数为几万亿时，数据量较大不适合全装入内存中，且无法容忍多次访问，所有数据只能访问一次，推荐使用最小堆法（上面那种情况也推荐使用这个方法），但要求K较小，否则无法在内存存下整个最小堆。

用容量为K的最小堆来存储最大的K个数，最小堆的堆顶元素就是最大K个数中最小的一个。每次考虑一个新的元素时，将其与堆顶的元素进行比较，只有当它大于堆顶元素时，才用其替换堆顶元素，并更新最小堆。时间复杂度为O(N*logK)。