3

我正试图通过外部排序来满足我的需求——但我做不到。

要求是对任意大小的文件进行外部排序，但仅使用原始文件和另一个文件（称为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]

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

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

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

4

2 回答 2

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）的句柄，同时逐个元素地读取它们，然后将它们写回一个已排序的合并数组（mergeListHandle1）。像这样：

[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和mergeListHandle2）的句柄，并不断合并它们，直到只剩下两个句柄，从而产生一个最终排序的数组。如果您想要基于代码的解决方案，请提供您的代码。

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

  1. 从 handle1 和 handle2 ( 1and 1)中读取第一个元素
  2. 将这两者中较小的写入mergedListHandle1（即1handle1的写入）
    1. 您目前可能不会刷新 mergeListHandle1 中的数字。
  3. 从 handle1 ( 5)中读取下一个元素
  4. 将句柄 1 和句柄 2 中较小的当前数字写入 mergeListHandle1
  5. 满时刷新mergedListHandle1的内容
  6. 从磁盘（handle3 和 handle4）中获取下一个较小的句柄，并在写入名为 mergeListHandle2 的新的较大列表句柄时对它们重复相同的循环。
于 2015-10-03T18:00:49.187 回答
1

简单的 2 路自下而上合并排序的说明。将数据视为大小为 1 的 18 次运行。由于大小为 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 个内存位置来保存数据，一个来自偶数运行的元素，一个来自奇数运行的元素。比较这两个元素，将较低或相等的元素写入目标文件，然后读取该运行的下一个元素。如果到达该运行的末尾，则写入另一个元素并将另一个运行的其余部分复制到目标文件。两个文件指针前进到下一对偶数和奇数运行的开始，并继续合并，直到到达数据末尾，结束合并过程。运行大小加倍，交换源文件和目标文件的角色，并完成下一次合并，重复直到运行大小>=元素数。

于 2015-10-04T09:48:48.350 回答