10

当我们对一个大文件进行外部合并排序时，我们将其拆分为小文件，对它们进行排序，然后将它们合并回一个大的排序文件。

合并时，我们可以进行多次 2 路合并，也可以进行一次多路合并。

我想知道哪种方法更好？为什么？

4

1 回答 1

7

一种多路合并通常更好。考虑三个小文件：

a1
a2
a3

和

b1
b2
b3

最后

c1
c2
c3

如果你用aand合并b，我们就剩下（比如说）

a1
b1
a2
b2
b3
a3

和

c1
c2
c3

最终合并将创建排序列表，但请注意在最终合并中我们必须再次访问a和b项目。正是这种重新合并在级联双向合并中是浪费的。

你可以做的是一个单一的多路合并。但是，请注意您的操作方式。具体来说，避免简单的双循环扫描每个光标以查看哪个具有最小值。请改用最小堆。这会将复杂性降低到O(n log n).

于 2012-08-04T06:39:32.773 回答