想象一下以下场景：我有一个存储在只读存储介质上的10Mb整数数组。我想把数字按升序打印出来。然而，我只有2Mb的主内存(没有硬盘)。
一个非常简单的O(n2)解决方案(不利用可用的主存储器)是重复扫描整个输入阵列并递增地输出下一个最小的整数。我试过在谷歌上搜索更好的排序算法，但答案一直让我选择原位或外部排序算法，由于只读存储的限制，这些算法不起作用。有更好的解决方案吗？
您可以使用主内存来显著减少扫描次数，并使用您给出的大小关系。
第一次扫描：用迄今为止发现的最小数字，在内存中保存一个几乎与主内存大小相同的存储。当存储尚未满时，添加从数组中读取的下一个数字。当商店已满时，与商店中最大的数字进行比较，如果新的数字较小，则删除最大的数字并添加新的数字。扫描完整个数组后，按顺序输出找到的数字，记住存储的最大数字以及该区块中发生的频率。
后续扫描：如果扫描的数字等于上一个区块中的最大数字，并且其出现次数小于上一次扫描的次数，则增加其出现次数，但不要将其添加到存储中，如果其出现次数大于或等于记住的次数，请将该数字添加到存储(如有必要，从存储中删除最大数字)。如果扫描的数字大于上次扫描的最大数字，但小于存储中的最大数字(或者存储尚未满)，请将其添加到存储中(如有必要，请删除最大数字)。扫描完成后，按顺序输出存储的数字，记住到目前为止输出的最大数字，以及它总共输出的数字(最大数字可能与上次扫描的数字相同，因此您需要知道到目前为止处理的所有块中输出的频率)。
我不确定存储的最佳数据结构是什么，但我认为堆是一个很好的选择(与maximum:O(1)相比，替换：O(日志大小)，对输出进行最终排序：O(大小*log大小)，实际上没有二进制搜索树的内存开销)。