c++ - 从非常大的未排序列表中获取最大 X 数的最快方法？

Question

我正在尝试从我的程序生成的分数列表中获得最高分，比如 100 分。不幸的是，该列表非常庞大(大约数百万到数十亿)，因此排序是该程序的时间密集型部分。

获得前 100 名分数的最佳排序方式是什么？

到目前为止我能想到的唯一两种方法是首先将所有分数生成一个庞大的数组，然后对其进行排序并取前 100 名。或者其次，生成 X 个分数，对其进行排序并截断前 100 名scores 然后继续生成更多分数，将它们添加到截断列表中，然后再次对其进行排序。

无论采用哪种方式，它仍然需要比我希望的更多的时间，关于如何以更有效的方式进行操作的任何想法？ (我以前从未上过编程类(class)，也许你们中那些拥有 comp sci 学位的人知道执行此操作的有效算法，至少这是我所希望的)。

最后，c++中标准sort()函数使用的排序算法是什么？

谢谢，

-伪造

编辑:只为所有好奇的人......

我在之前和之后做了一些时间试验，结果如下:

旧程序(在每次外循环迭代后进行排序):

top 100 scores: 147 seconds
top  10 scores: 147 seconds
top   1 scores: 146 seconds
Sorting disabled: 55 seconds

新程序(仅跟踪最高分并使用默认排序功能):

top 100 scores: 350 seconds <-- hmm...worse than before
top  10 scores: 103 seconds 
top   1 scores:  69 seconds 
Sorting disabled: 51 seconds

新改写(数据存储优化，手写排序算法):

top 100 scores: 71 seconds <-- Very nice!
top  10 scores: 52 seconds
top   1 scores: 51 seconds
Sorting disabled: 50 seconds

在核心 2、1.6 GHz 上完成...我等不及我的核心 i7 860 到货了...

还有很多其他更积极的优化需要我解决(主要是在减少我运行的迭代次数方面)，但就目前而言，速度已经足够好了，我可能不会甚至费心去计算那些算法优化。

感谢每个人的投入!

Answer 1

1. 取前 100 个分数，并将它们排序到一个数组中。
2. 获取下一个分数，并将其插入排序到数组中(从“小”端开始)
3. 删除第 101 个值
4. 继续下一个值，在 2，直到完成

随着时间的推移，列表会越来越像前 100 个最大值，所以更多时候，你会发现插入排序立即中止，发现新值小于前 100 个候选值的最小值。