【参考答案】讨论9.1 堆排序最适合解决什么样的问题？

<p>如果我们要从全球70多亿人口中找出最富有的100个人，有什么排序算法可以保证不用完全排序就能在中途得到结果吗？</p><p><br ></p><p>插入排序不行：如果最大富翁最后才出现，那么不到最后一步完成，我们都不敢保证说前面100个就是答案了。</p><p><br ></p><p>希尔排序本质上是插入的变形，肯定也是不行。</p><p><br ></p><p>归并呢？因为前后两半的元素在整个排序中不会串边，所以只要后半部分有大富翁，就一定得等到最后一步大合并，才能确保前面排的100个是答案。</p><p><br ></p><p>而堆排序是唯一可以只用100步就保证得到前100个大富翁的算法！当然，在排序之前先要O(N)的时间去建立最大堆。</p><p><br ></p><p>所以当我们的问题是要从大量的N个数据中找最大/最小的k个元素时，用堆排序是比较快的，可以在O(N+klogN)时间内得到解 —— 当然k比较小才行。对于这种问题，还有另一种方法是：先把前k个元素调整成最小堆（时间为O(k)）；此后每读入一个元素，首先跟堆顶元素比较，如果没有堆顶大，就直接扔掉了；否则把堆顶元素替换掉，做一次下滤。这样总体最坏复杂度是O(k+Nlogk)。</p><p><br ></p>