使用K路归并合并N个已排序文件

Question

有很多关于合并排序文件或合并K个排序文件的文献。它们都是根据以下理论工作的：将每个文件的第一个元素放入堆中，然后直到堆为空，弹出该元素，并从该元素所在的文件获取另一个元素。只要可以将每个文件的一个记录放入堆中，这种方法就有效。

现在假设我有N个排序文件，但我只能将K条记录放入堆中，其中K＜N，且假设N = Kc，其中“c”是乘数，表示N很大，是c的某个倍数。显然，需要一遍又一遍地进行K路合并，直到最终只剩下K个文件，然后将它们合并为最终排序文件。如何实现这个过程以及复杂度是多少呢？

- curiousengineer

---

该程序每次会合并k个文件。令n = 1024，k = 16。第一次合并16个文件，结果得到64个文件。第二次也是每次合并16个文件，结果得到4个文件。最后一次是4路合并，生成单个文件。 - rcgldr

谢谢，我能找到这个的Java实现的例子吗？ - curiousengineer

Answer 1

有多个用Java编写的K路合并示例。其中一个是http://www.sanfoundry.com/java-program-k-way-merge-algorithm/。

为了实现您的合并，您只需要编写一个简单的包装器，不断扫描目录，将文件合并，直到只剩下一个文件。基本思想是：

while number of files > 1
    fileList = Load all file names
    i = 0
    while i < fileList.length
        filesToMerge = copy files i through i+k-1 from file list
        merge(filesToMerge, output file name)
        i += k
    end while
end while

复杂度分析

如果我们假设每个文件包含相同数量的项，那么这会更容易理解。

您需要合并M个文件，每个文件包含n个项目，但是您一次只能合并k个文件。因此，您需要执行log_k(M)次操作。也就是说，如果您有1,024个文件，每次只能合并16个文件，则您将进行一次合并16个文件的操作，创建总共64个文件。然后，您将进行另一次合并16个文件的操作，创建4个文件，最后一次合并这4个文件以创建输出。

如果您有k个包含n个项目的文件，则将它们合并的复杂度为O(n*k log₂ k)。

因此，在第一次操作中，您要执行M/k次合并，每次合并的复杂度为O(nk log k)。这是O((M/k) * n * k * log₂ k)，或者O(Mn log k)。

现在，每个文件都包含nkk个项目，并且您要对每个k个文件进行M/k/k次合并。因此，第二次操作的复杂度为O((M/k²) n * k² * log₂ k)。简化后，这也等于O(Mn log k)。

在第二次操作中，您要执行k次合并，每次合并的复杂度为O(nk)。请注意，在每个操作中，您都在处理M*n个项目。因此，每次操作的复杂度都是O(Mn log k)。而您要执行log_k(M)次操作。因此，总复杂度为：O(log_k(M) * (Mn log k))，或者

O((Mn log k) log M)

假设每个文件包含相同数量的项目并不影响渐进分析，因为，正如我所展示的那样，每个传递操作相同数量的项目：M*n。

- Jim Mischel

---

不错的答案。在看完复杂性之后，我意识到另一种将此合并可视化的方法是将复杂性重写为O((M x Log(M)) x (n x Log(k)))。然后从 M x Log(M) 可以看出它实际上是 M 个“文件项”的合并。由于在每个合并级别中，有 n 个项目以 k 个为一组进行合并，因此您可以得到复杂性的第二部分 - n x Log(k)。 - displayName

Answer 2

这是我所有的想法

我会使用迭代来完成。首先，我会进行 p=floor(n/k) 次迭代，以获取 p 个已排序的文件。然后继续对 p+n%k 个项目执行此操作，直到 p+n%k 变得小于 k。最后，将获得已排序的文件。

这有意义吗？

- Md Monjur Ul Hasan