算术

设计一个选择算法从一组N个数字中找出最大或最小的M个数字。M通常远远小于N。

类似的问题往往是和缓存的使用有关。比如搜索引擎对常用搜索结果需要进行缓存，以避免反复的重复查询。比较简单的策略可以是对最后的M个不同的搜索进行缓存。这样的性能并非最优的，因为最后的M个搜索并不一定是最频繁的搜索。比较好的方案是对所有搜索计算出现的频率，然后选出最频率最高的M个进行缓存。当然这一过程并不需要是实时的，比如每天做一次就差不多了。两种方案如果能结合以下，量增缓存的效果可能会更好。

常用的算法有几个，最简单的是基于堆排序的方法。堆排序中每一步可以发现一个最大或最小值，复杂度为O(log N)，然后将其移出堆外，在对剩下的数据重复同样的操作。总的计算复杂度为O(M log N)。需要注意的是，一开始建立堆的过程可能需要O(log N)时间，所以如果M很小的话，可能不很划算。

另外有一些速度比较快的算法：

• 基于快速排序的方法。快速排序中每一步将数据分割成两部分，一部分大于分割点，另一部分小于分割点。我们可以很容易的判断第M大/小数字位于那个区间，因而另一个区间就不需要再处理了。这个方法的平均复杂度为O(N)。产生的M个数字的顺序是不确定的。
• 排序与扫描相结合的办法。我们可以用一个堆或者二叉树来维护当前已知的最大（或最小）的M个数，然后在扫描数据的过程中，将每个新的数字和这M个数中最小的（或最大的）进行比较，需要时替换这个数字。每次替换时，维护堆或者二叉树的成本为O(log M)，因为最多进行N次替换，所以最坏复杂度为O(N log M)。另外这个堆可以直接放在原始数组的开头，不需占用额外空间。

由于一般N>>M，当M较小的时候后一个方法可能比较好，当M较大的时候基于快速排序方法应该较快。更多的细节可以参考Wikipedia的文章。