我正试图通过外部排序来满足我的需求——但我做不到。
要求是对任意大小的文件进行外部排序,但仅使用原始文件和另一个文件(称为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]
但是,如果我一次只能将四个页面放入内存中,我看不出如何在没有一些可怕的复杂算法的情况下进一步对它们进行排序,该算法一次又一次地循环整个数组以确保其全部排序。
我完全糊涂了——因为如果不将整个数组读入内存,我们不知道四页之前或之后的元素是什么——所以我们不能真正对它们进行排序?
有人可以帮我解释解决这个问题的关键步骤吗?