想象以下场景:我有一个 10 Mb 的整数数组存储在只读存储介质上。我希望按升序打印出数字。但是，我只有 2 Mb 的主内存(没有硬盘)。
一个非常简单的 O(n2) 解决方案(不使用可用的主内存)是重复扫描整个输入数组并递增输出下一个最小整数。我已经尝试使用谷歌搜索更好的排序算法，但答案一直引导我使用就地或外部排序算法，由于只读存储限制，这些算法不起作用。有更好的解决方案吗？
最佳答案
您可以使用主内存来减少扫描次数，根据您给出的大小关系，非常显着。
第一次扫描:保留一个接近主内存大小的内存存储，其中包含迄今为止找到的最小数字。当存储尚未满时，添加从数组中读取的下一个数字。当商店已满时，与商店中最大的数字进行比较，如果新的数字较小，则删除最大的数字并添加新的数字。扫描完整个数组后，按顺序输出找到的数字，记住存储的最大数字以及该 block 中出现的频率。
后续扫描:如果扫描的数量等于前一个 block 的最大数量，并且它的出现次数小于上一次扫描的次数，则增加它的出现次数，但不要将它添加到存储中，如果它出现计数大于或等于记住的计数将数字添加到存储中(如有必要，从存储中删除最大的数字)。如果扫描到的数大于上次扫描的最大数，但小于店内最大数(或店内未满)，则将其加入店内(必要时删除最大数)。扫描完成后，按顺序输出存储的数字，记住目前输出的最大数字，以及总共输出的数字(最大数字可能与上次扫描的数字相同，所以需要了解它在目前处理的所有 block 中的输出频率)。
我不确定存储的最佳数据结构是什么，但我认为堆是一个不错的选择(与最大比较:O(1)，替换为:O(log size)，最终排序为输出:O(size*log size)，几乎没有二叉搜索树的内存开销。
关于algorithm - 有限内存和只读磁盘排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12487038/