algorithm - 如何对可变长度的大句子文件进行排序？

Question

假设我有一个包含很多行字符串的文件，如何按照字典顺序对字符串行进行排序？

详细信息:

• 文件大小约为32GBytes；
• 每一行可视为一个句子，由空格分隔的单词个数可变，即每一行的长度不固定；
• 每个单词只包含 ASCII 字符；
• 我只有 8 GBytes 的内存，但没有无限的磁盘空间；

我能弄清楚的是外部归并排序，对于这个特定问题有没有更好的主意？

Answer 1

文件大小和内存之间的差异并不大，因此我建议根据首字母将文件拆分为更多较小的文件 - 或者如果不够，则根据前两个字母拆分。

然后您可以使用快速排序对它们中的每一个进行排序并保存，然后当它们被排序时，您可以将它们放回一起。

仍然是 O(N) 次 I/O 操作和 O(n*log(N)) 次 CPU 操作。

PS:外部归并排序也是一个好方法。