algorithm - 最多排序 1000 万个 7 位数字。约束 : 1M RAM, 高速。几秒就好

Question

对最多 1000 万个 7 位数字进行排序。约束条件:1M RAM，高速。几秒就好。

[编辑:来自提问者的评论:输入值不同]

使用位图数据结构可以很好地解决这个问题。

这意味着我需要一个字符串，它的长度最多为 1000 万？？？？那么 RAM 是否足够？在这里困惑。谢谢

Answer 1

因此，1MB 中有大约 8,000,000 位，但如果您有任意 7 位数字(最多 9,999,999)，则使用位向量进行排序将不起作用。同样，如果某些数字可以重复，它也不起作用，因为您只能将 {0,1} 存储在位向量中。

但是假设(我认为你的问题是问什么)你有一个介于 0 和 8,000,000 之间且没有重复的整数序列，你可以简单地分配一个 8,000,000 位的归零数组，然后为每个数字勾选相应的数组中的位。然后输出排序后的列表就是简单地按顺序读取该数组并输出每个 1 值的索引。

如果你问的是更复杂的问题(0 - 1000 万，允许重复)，那么你需要对适合 ram 的 block 进行排序，将它们存储在磁盘上，然后你可以将这些 block 合并到线性时间和流式传输(因此您不必将整个内容存储在内存中)。这是一个非常相似的东西在 python 中的实现:http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html