如何在不使用磁盘、网络或虚拟内存的情况下对大文件进行排序？

Question

昨天，我参加了一次关于网络安全职位的面试，并提出了以下问题：

假设您有一个1GB内存的PC，这台计算机的磁盘包含一个10 GB的文件，其中包含随机数。您将使用什么技术来对文件进行排序并提出算法。您不能使用磁盘、网络或虚拟内存进行排序？。

我尝试了许多我能想到的不同的方法，建议外部分类，但面试官说这不是正确的方法。面试结束时，我礼貌地问他，他问我的问题的方式和算法是什么，但他拒绝说，好像这是某种大秘密。

我的问题是，有人会如何处理这样的问题，因为我只是不停地思考，但仍然没有明确的答案。

Answer 1

要对文件进行排序，需要在RAM中运行算法。因为文件比可用的RAM大10倍，所以需要将文件排序为10个(或更多)独立块，并在最后重新组合它们。

你的算法需要由..。

1. 阅读光盘上的列表，查找文件中最大的数字(并在阅读列表后跟踪它)
2. 在阅读完整个列表之后，将这个数字放入RAM中的一个列表中，然后重复这个过程(每次寻找小于最后一个的最大数目)，直到全部或大部分RAM用完为止。
3. 现在，将该列表添加回磁盘，并使用表示其顺序的索引(在本例中为1 )，并清除RAM以进行更多处理。
4. 每次在RAM上构建排序数字列表时，重复步骤3、10倍或更多，直到所有数字都添加到磁盘上的单独列表中为止。
5. 要完成这些工作，请检查每个列表开头的索引，并(每次一个列表)在磁盘上按正确的顺序排列索引。

更新:我在我的回答中添加了以反映@JimMischel提出的一些观点

RAM中的算法不仅要跟踪最大的数字，而且还要保持一个单独的整数计数，这个整数计数将随着文件中随后发生的每一个数字的出现而增加。然后，这个数字将被放置在RAM中的子列表中，但是这个数字会出现很多次。

更新:关于提问者问题的

OP发布的问题指出，“您不能使用磁盘进行排序”。问题是，没有任何暗示光盘不能用于存储的东西。我相信大多数阅读这个问题的人都错误地解释了这一点，因此，如果没有存储任何数据的地方，就认为分配的任务是不可能完成的。