4

有关于合并排序文件或合并 K 排序文件的不错的文献。他们都基于这样一个理论，即每个文件的第一个元素都放在一个堆中，然后直到堆为空轮询该元素，然后从该元素所在的文件中获取另一个元素。只要可以将每个文件的一条记录放在堆中，这就会起作用。

现在让我们说我有 N 个已排序的文件，但我只能将 K 条记录放入堆中并且 K < N 并让我们说 N = Kc 其中“c”是乘数，意味着 N 太大以至于它是 c 的某个倍数. 显然，它需要一遍又一遍地进行 K 路合并，直到我们只剩下 K 个文件，然后我们将它们作为最后一次合并到最终排序中。我如何实现这一点，这将是什么复杂性？

4

2 回答 2

3

有多个用 Java 编写的 k-way 合并示例。一个是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) pass。也就是说，如果您有 1,024 个文件并且一次只能合并 16 个，那么您将进行一次合并 16 个文件的过程，总共创建 64 个文件。然后，您将进行另一遍，一次合并 16 个文件，创建四个文件，最后一遍将合并这四个文件以创建输出。

如果你有 k 个文件，每个文件包含 n 个项目，那么合并它们的复杂度是 O(n*k log 2 k)。

因此，在第一遍中，您进行 M/k 合并，每个合并的复杂度为 O(nk log k)。那是 O((M/k) * n * k * log 2 k)，或 O(Mn log k)。

现在，您的每个文件都包含 n k k 个项目，并且您每个都对 k 个文件进行 M/k/k 合并。所以第二遍复杂度是 O((M/k 2 ) n * k 2 * log 2 k)。简化后，这也适用于 O(Mn log k)。

在第二遍中，您进行 k 次合并，每个合并的复杂度为 O(nk)。请注意，在每次传递中，您都在使用 M*n 项。所以你做的每一遍都是O（Mn log k）。你正在做 log k (M) pass。所以总复杂度是：O(log k (M) * (Mn log k))，或者

O((Mn log k) log M)

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

于 2017-12-22T15:05:56.017 回答
-1

这是我所有的想法

我会在迭代中做到这一点。首先，我会进行 p=floor(n/k) 迭代以获取 p 排序文件。然后继续对 p+n%k 个项目执行此操作，直到 p+n%k 变得小于 k。然后最后会得到排序后的文件。

是否有意义？

于 2017-12-22T04:51:50.550 回答