两个文件之间的外部排序

Question

我正在尝试根据我的要求进行外部排序 - 但我做不到。

要求是对任意大小的文件进行外部排序，但只使用原始文件和另一个文件（称它们为 fileA 和 fileB）- 两个文件包括原始文件。我可以 read/write 中的任何一个 - 所以可以在两者之间交换...

我不知道如何实现它 - 因为大多数排序算法都要求您能够概览内存中的整个数组才能对其进行排序，对吧？

假设我有一个随机整数数组：

[1, 5, 8, 7, 3, 4, 1, 9, 0, 1, 8, 7, 7, 3, 2, 9, 1, 2];

并且在任何给定时间，我只能将四页（例如四个整数）读入内存。

每次通过时，这都会给我五个单独的数组进行排序：

[1, 5, 8, 7]
[3, 4, 1, 9] 
[0, 1, 8, 7] 
[7, 3, 2, 9]
[1, 2]

如果我对这些应用内存排序，我会得到：

[1, 5, 7, 8]
[1, 3, 4, 9] 
[0, 1, 7, 8] 
[2, 3, 7, 9]
[1, 2]

但是如果我一次只能将四个页面放入内存，我不知道如何在没有一些可怕的复杂算法的情况下进一步对它们进行排序，该算法一次又一次地遍历整个数组以确保其全部排序.

我完全糊涂了 - 因为如果不将整个数组读入内存，我们不知道四页之前或之后的元素是什么 - 所以我们无法真正对它们进行排序？

有人可以帮我解释一下解决这个问题的关键步骤吗？

Answer 1

由于外部排序的基本思想是合并大于可用内存的列表，因此您可以通过处理他们。为了从列表中读取元素，您将使用一些方法，例如 listHandle.getNextElement()。要写入列表中的磁盘，请使用 mergedDoubleSizedList.writeNextElement().

在你拥有之后：

[1, 5, 7, 8] // controlled using handle1
[1, 3, 4, 9] // controlled using handle2
[0, 1, 7, 8] // controlled using handle3
[2, 3, 7, 9] // controlled using handle4
[1, 2] // controlled using handle5

并且你只读了 4 个整数，你得到了前两个数组的句柄（handle1 和 handle2），阅读它们同时逐个元素，并将它们作为一个排序的合并数组写回（mergedListHandle1）。像这样：

[1, 1, 3, 4, 5, 7, 8, 9] // written by creating new handle - mergedListHandle1
[0, 1, 2, 3, 7, 7, 8, 9] // written by creating - mergedListHandle2
[1, 2] // written back by creating mergedListHandle3

现在您再次获得了上一步产生的两个数组的句柄（mergedListHandle1 和 mergedListHandle2）并继续合并它们一直进行下去，直到只剩下两个句柄，从而得到一个最终的排序数组。如果您想要基于代码的解决方案，请提供您的代码。

一次，如果您的记忆允许的话，您的记忆中将只有 4 个元素。因此，要合并由 handle1 和 handle2 表示的列表，您将执行以下操作：

从 handle1 和 handle2（1 和 1）读取第一个元素
将两者中较小的写入mergedListHandle1（即写入handle1的1）
1. 您目前不能刷新 mergedListHandle1 中的数字。
从 handle1 读取下一个元素 (5)
将handle1和handle2中当前数字中较小的写入mergedListHandle1
mergedListHandle1 已满时刷新其内容
从磁盘（handle3 和 handle4）获取下一个较小的句柄，并在写入名为 mergedListHandle2 的新的较大列表句柄时对它们重复相同的循环。

Answer 2

简单的 2 种自下而上归并排序的说明。将数据视为大小为 1 的 18 运行s。由于大小为 1，因此每个运行都可以视为已排序。

[1] [5] [8] [7] [3] [4] [1] [9] [0] [1] [8] [7] [7] [3] [2] [9] [1] [2]

在每一遍中，偶数运行与奇数运行从左到右从源数组或文件合并到目标数组或文件中。每次通过后，交换源和目标的角色。

第一关

[1 5] [7 8] [3 4] [1 9] [0 1] [7 8] [3 7] [2 9] [1 2]

第二遍

[1 5 7 8] [1 3 4 9] [0 1 7 8] [2 3 7 9] [1 2]

第三遍

[1 1 3 4 5 7 8 9] [0 1 2 3 7 7 8 9] [1 2]

第四关

[0 1 1 1 2 3 3 4 5 7 7 7 8 8 9 9] [1 2]

第五遍（完成）

[0 1 1 1 1 2 2 3 3 4 5 7 7 7 8 8 9 9]

主要变量是运行大小，以及一对运行开始和结束的 4 个索引（偶数和奇数）。最后一个运行在数据末尾结束，可以是偶数或奇数运行。对于外部排序，索引成为文件指针。

外部排序只需要 2 个内存位置来保存数据，一个元素来自偶数运行，一个元素来自奇数运行。比较两个元素，将较低或等于的元素写入目标文件，然后读取运行中的下一个元素。如果到达运行的末尾，则写入另一个元素，并将另一个运行的其余部分复制到目标文件。两个文件指针前进到下一对偶数和奇数运行的开始，并继续合并，直到到达数据末尾，结束合并过程。运行大小加倍，交换源文件和目标文件的角色，完成下一个合并过程，重复直到运行大小变为 >= 元素数。

两个文件之间的外部排序

External Sort between two files

arrays

sorting

algorithm

external-sorting