高效的算法来排序文件记录

Question

我有一个文件,其中包含不同长度的记录数.什么是对这些记录进行排序的有效算法.

记录样本:

000000000000dc01 t error_handling 44

0000000dfa01a000 t fun 44

总记录=> 5000编程语言c

我想知道哪种算法适合根据地址对此文件进行排序,以及读取这些记录的有效方法是什么？

Answer 1

如果文件太大而无法放入内存,那么您唯一合理的选择是基于文件的合并排序,它涉及两次传递.

在第一遍中,读取N个记录的块(其中N被定义为适合内存的记录数),对它们进行排序,并将它们写入临时文件.完成此传递后,您可以拥有一个临时文件的编号(称为M),每个临时文件都有不同数量的已排序记录,或者您有一个包含已排序记录块的临时文件.

第二遍是M-way合并.

我在一段时间后写了一篇关于如何使用文本文件执行此操作的文章.请参阅排序大文本文件.扩展它是相当简单的,这样它将对您定义的其他类型的记录进行排序.

有关更多信息,请参阅外部排序.