问题描述 ​

如何在 1 亿个数中找出最大的 10000 个数？

解决方法 ​

1. 快速排序法 ​

直接对所有数据进行快速排序，然后取前 10000 个数，时间复杂度为 O(nlong~n~)。

机器内存可以撑住，但是效率不高，不推荐使用。

2. 淘汰法 ​

用一个 list 保存前 10000 个数字，然后遍历剩下的数字，如果某一个数字比容器中的最小值要大，就替换它。

从容器中找到最小值的时间复杂度是 O(10000)，替换一次之后，又需要重新找最小值；整体时间复杂度较高，不推荐使用。

3. 分治法 ​

1. 将 1 亿个数据分成 100 份，每份 100 万个数据；
2. 然后使用多线程使用快速排序找出每份中 10000 个最大的数；
3. 最后在找出的所有数据中，使用快速排序找出最大的 10000 个。

这样可以提高 CPU 的利用率，大幅提高效率，推荐使用。

4. 堆排序 ​

1. 首先读取 10000 个数来构建一个最小堆（因为堆顶元素是堆里最小的，其他的都它大），建堆的时间复杂度为 O(mlongm) (m 为数组大小即为 10000)；
2. 遍历其他的数据，如果小于堆顶元素，则用该元素替换它，然后重新构建最小堆；
3. 重复上述步骤，直至所有数据被遍历完。
4. 中序遍历堆得到的结果就是有序的。

上述方法的时间复杂度为 O(nmlogm)，空间复杂度为 O(10000)，推荐使用。