arrays - 两个文件之间的外部排序

Question

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

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

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

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

[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 表示的列表，您需要执行以下操作:

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