用于外部排序的 C# N 方式合并

Question

对 N 个排序的文件实现 N 路合并的最佳方法是什么？

假设我有 9 个排序文件，每个文件有 10 条记录？如何合并这些文件以创建一个包含 90 条排序记录的大文件？

Answer 1

我假设可能有比您在示例中提供的数据更多的数据。如果您可以同时打开所有文件，则可以使用此算法:

• 从每个文件中读取第一行，因此内存中有 10 行，每个文件一行。
• 按排序顺序将行放入优先队列。
• 从优先级队列中取出最少的元素(排序在前)并写入输出文件。
• 从该行所在的相应文件中再读取一行并将其放入优先级队列。
• 重复直到所有文件都读完。

请注意，您不必一次将所有文件读入内存，因此如果您有合理数量的大文件，这会很有效，但如果您有很多小文件，则效果不佳。

如果你有很多小文件，你应该将它们分组合并，为每个组制作一个输出文件，然后重复这个过程来合并这些新的组。

在 C# 中，您可以使用例如 SortedDictionary 来实现优先级队列。