《编程之美》读书笔记07： 2.5 寻找最大的K个数 - 雁过无痕 - C++博客

问题：

从n个数中找出最大的k个数。

 

两种思路：

1 保存目前找到的最大k个数，每访问一个数，就与这k个数中的最小值比较，决定是否更新这k个数。储存k个数的数据结构可采用：败者树、二叉查找树、最小堆。

C++ STL提供了multiset和priority_queue容器，另外还提供了make_heap，push_heap，pop_heap方便手动构建堆结构。（测试发现，手工建堆的效率最高，当n和k增大到一定值时，采用红黑树的multiset的效率极差。手动建堆的效率相比priority_queue有略微提高。）

 

2 修改排序方法，去除不必要的过程。

选择排序： 只要选k次。

冒泡排序： 只要冒泡k次即可。

堆排序：   构建好最大堆后，取 k次最大值

快速排序： 分区时，根据数P将数组分为两部分，设大于P的数个数为a，小于P的数的个数为b。如果，a>=k，则从这a个数取最大的k个数，若a<k，则从b个数取最大的k-a-1个。

归并排序： 当待合并的两个数组，两数组长度和大等于k时，合并时只取前k个。或者：以(k+1)/2个数为一组，将数组分成几个组，对每组进行排序（可以采用任何一种高效的排序方法）后，两两合并时只取前k个。

计数排序： 如果都是整数，先扫描一遍找出最大值max，最小值min，再扫一遍，将每个值减去min，对这个值计数，最后从max-min开始统计，找出最大的k个数。另外，也可采用桶排序。

桶排序：   可以不对桶内的数据进行排序。

基数排序： 可以采用最高关键字比较方法，并免去相关的排序。

 

STL中的nth_element就是基于对intorsort的修改（introtsort是对快速排序的改进，当递归深度达到一定值时，可切换到堆排序），而partial_sort和partial_sort_copy是基于堆排序的修改，因而在k很小时，其效率可能会高于nth_element。遗憾的是：STL没有提供完全基于堆排序的nth_element。

 

从下面的测试结果，可以看出：在M不是很大，M/N很小时，partial_sort和partial_sort_copy尽管多了"对堆结构进行排序"这个不必要的操作，其效率仍然高于nth_element，但相差不多。而在其它情况下nth_element的效率则比其它的几种方法要高很多。

 

如果源数据都是整数，多数情况下（即使允许修改源数据），桶排序方法（结合计数方法）的效率比nth_element高。桶排序只需256K的内存，效率很高。在M和N至少有一个大于当前内存大小的情况下，桶排序是最佳选择，其性能远高于其它方法。

 

如果源数据是浮点数，根据浮点数在内存中的表示，可以对桶排序方法进行适当修改，使之对浮点数也适用。

Read full article from 《编程之美》读书笔记07： 2.5 寻找最大的K个数 - 雁过无痕 - C++博客