百度面试题：在100w个数中找最大的前100个数

在100w个数中找最大的前100个数

答案在文章评论部分，请注意查看:)

原文网址：http://hi.baidu.com/mianshiti/blog/item/37652f27a3ac4320d5074252.html

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

2.5 寻找最大的K个数

从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至少有一个大于当前内存大小的情况下，桶排序是最佳选择，其性能远高于其它方法。

测试结果说明：测试程序要求不得改变源数据，某些方法要多一个复制源数据操作，可以从partial_sort_copy和partial_sort效率的差异，看出这个复制操作的影响。桶排序方法对应nth_count；对堆结构的调整，采用三种途径（分别对应三个程序）：利用push_heap和pop_heap、只用pop_heap、手写代码调整。（测试了几次，multiset和heapsort方法，在相同N和M情况下，所用时间起伏很大，即所用时间对原始数据依赖性很高。）

测试代码

N,M: 1000000 800000 0.8

Randomizing: 78 ms

nth_elmemnt 16 ms

nth_count 16 ms

priority_queue 47 ms

partial_sort 125 ms

partial_sort_copy 110 ms

heap(pop/push) 31 ms

heap(pop/copy) 32 ms

heap(custom_pop) 31 ms

multiset 484 ms

heap_sort 172 ms

N,M: 100000000 10000 0.0001

Randomizing: 5453 ms

nth_elmemnt 1828 ms

nth_count 750 ms

priority_queue 406 ms

partial_sort 844 ms

partial_sort_copy 328 ms

heap(pop/push) 203 ms

heap(pop/copy) 375 ms

heap(custom_pop) 391 ms

multiset 375 ms

heap_sort 4015 ms

N,M: 100000000 10000 0.0001

Randomizing: 5454 ms

nth_elmemnt 1796 ms

nth_count 766 ms

priority_queue 391 ms

partial_sort 843 ms

partial_sort_copy 344 ms

heap(pop/push) 188 ms

heap(pop/copy) 375 ms

heap(custom_pop) 390 ms

multiset 375 ms

heap_sort 4016 ms

N,M: 100000000 100000 0.001

Randomizing: 5453 ms

nth_elmemnt 1719 ms

nth_count 750 ms

priority_queue 406 ms

partial_sort 844 ms

partial_sort_copy 343 ms

heap(pop/push) 187 ms

heap(pop/copy) 375 ms

heap(custom_pop) 391 ms

multiset 438 ms

heap_sort 4234 ms

N,M: 100000000 100000 0.001

Randomizing: 5438 ms

nth_elmemnt 1719 ms

nth_count 750 ms

priority_queue 406 ms

partial_sort 860 ms

partial_sort_copy 343 ms

heap(pop/push) 203 ms

heap(pop/copy) 360 ms

heap(custom_pop) 390 ms

multiset 438 ms

heap_sort 4078 ms

N,M: 100000000 1000000 0.01

Randomizing: 5453 ms

nth_elmemnt 1735 ms

nth_count 765 ms

priority_queue 438 ms

partial_sort 1125 ms

partial_sort_copy 515 ms

heap(pop/push) 204 ms

heap(pop/copy) 406 ms

heap(custom_pop) 422 ms

multiset 1031 ms

heap_sort 4797 ms

N,M: 100000000 1000000 0.01

Randomizing: 5453 ms

nth_elmemnt 1797 ms

nth_count 781 ms

priority_queue 454 ms

partial_sort 1140 ms

partial_sort_copy 531 ms

heap(pop/push) 204 ms

heap(pop/copy) 406 ms

heap(custom_pop) 437 ms

multiset 1032 ms

heap_sort 4828 ms

N,M: 100000000 5000000 0.05

Randomizing: 5469 ms

nth_elmemnt 1781 ms

nth_count 782 ms

priority_queue 610 ms

partial_sort 1953 ms

partial_sort_copy 3578 ms

heap(pop/push) 344 ms

heap(pop/copy) 593 ms

heap(custom_pop) 578 ms

multiset 3641 ms

heap_sort 9391 ms

N,M: 100000000 5000000 0.05

Randomizing: 5469 ms

nth_elmemnt 1750 ms

nth_count 797 ms

priority_queue 625 ms

partial_sort 1953 ms

partial_sort_copy 3562 ms

heap(pop/push) 344 ms

heap(pop/copy) 578 ms

heap(custom_pop) 578 ms

multiset 3625 ms

heap_sort 9406 ms