algorithm - 置换外部存储器的实用算法

Question

在一个旋转的磁盘上，我有 N 条记录要排列。在 RAM 中，我有一个包含 N 个索引的数组，其中包含所需的排列。我也有足够的 RAM 一次保存 n 条记录。考虑到顺序磁盘访问要快得多这一事实，我可以使用什么算法尽快在磁盘上执行排列？

如果需要，我有足够的磁盘空间用于中间文件。

Answer 1

这是一个已知问题。在您的排列顺序中找到循环。例如，给定五个要排列 [1, 0, 3, 4, 2] 的记录，您有循环 (0, 1) 和 (2, 3, 4)。您可以通过选择一个未使用的起始位置来做到这一点；跟随索引指针，直到返回起点。指针序列描述了一个循环。

然后您用一个内部临时变量排列记录，一个记录长。

temp = disk[0]
disk[0] = disk[1]
disk[1] = temp

temp = disk[2] 
disk[2] = disk[3]
disk[3] = disk[4]
disk[4] = temp

请注意，您还可以在遍历指针时执行排列。您还需要一些方法来调用哪些位置已经排列，例如清除排列索引(将其设置为 -1)。

你能看出如何概括吗？