在 C++ 中,假设我们知道数字的范围,是否可以仅使用 100,000 个存储单元对 100 万个数字进行排序?
具体来说,一个.bin文件包含给定范围内的一百万个数字,需要将这些数字按降序排列到另一个.bin文件中,但我只允许使用大小为100,000的数组进行排序。有什么想法吗?
最佳答案
我想我在 SO 或 Quora 的某处读到了关于 map-reduce 的内容:
除以 100 万。数字分成 10 个 block 。读入第一个 100k 数字 block ,使用快速排序对其进行排序,然后将其写回原始文件。对其余 9 个 block 执行相同的步骤。然后对原始文件中的 10 个排序 block 执行 10 向合并(为此你只需要 10 个单元格)并将合并的输出写入另一个文件。您可以写入约 100k 的缓冲区,然后将其刷新到输出文件以加快写入速度。
关于c++ - 仅用 10 万个存储单元对 100 万个数字进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42454790/