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

我正在尝试从我的程序生成的分数列表中获得100分.不幸的是,这个列表是巨大的(数百万到数十亿),所以排序是程序的一个时间密集的部分.

做排序的最佳方法是获得前100名成绩？

到目前为止,我可以想到的唯一的两种方法是先将所有分数全部生成一个庞大阵列,然后将其排序并排在前100位.或者第二,生成X个分数,排序并截断前100个分数,然后继续产生更多分数,将它们添加到截断的列表中,然后再次排序.

无论哪种方式,我都会这样做,还需要更多的时间比我想要的任何想法如何以更有效的方式做到这一点？ (我从来没有参加过编程课程,也许那些具有comp sci学位的人都知道有效的算法来做到这一点,至少这是我希望的).

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

谢谢,

-Faken

编辑：只是为任何人好奇…

我在前后做过几次试验,结果如下：

旧程序(每个外循环迭代后的预制排序)：

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到达…

对于我来说,还有很多其他更加积极的优化(主要是在减少我运行的迭代次数的方面),但是像现在这样,速度还不够好,我甚至不会打扰制定出这些算法优化.

感谢eveyrone的输入！