如何排序(百万/十亿/ ...)整数？

Question

有时,访问者会询问如何对数百万/十亿32位整数进行排序(例如此处和此处).我猜他们希望候选人将O(N Log(N))排序与基数排序进行比较.对于百万个整数,O(N Log(N))排序可能更好,但对于十亿,它们可能是相同的.是否有意义 ？

Answer 1

如果你得到这样的问题,他们就不会找到答案.他们想要做的是看你如何思考问题.你是否直接进入,或者你是否对项目要求提出疑问？

你最好问的一个问题是,"问题解决方案需要多么优化？" 也许存储在文件中的冒泡记录就足够了,但你必须要问.如果输入更改为64位数,如果排序过程可以轻松更新,请询问问题？询问程序员开发程序需要多长时间.

这些类型的问题向我表明,候选人有足够的智慧,看到问题不仅仅是排序数字.

Answer 2

我希望他们能够扩大内部排序和外部排序之间的差异.显然,人们不读克努特现在

Answer 3

正如aaaa bbbb所说，这取决于情况。您会询问有关项目要求的问题。比如要统计员工的年龄，你大概用的是Counting sort，我可以把内存中的数据排序。但是当数据完全随机时，您可能会使用外部排序。例如，您可以将源文件的数据分成不同的文件，每个文件都有一个唯一的范围（File1 是从 0-1m，File2 是从 1m+1 - 2m 等），然后对每个文件进行排序，最后将它们合并到一个新文件中。

Answer 4

使用位图。您需要大约 500 Mb 来表示整个 32 位整数范围。对于给定数组中的每个整数，只需设置相应的位。然后只需从左到右扫描位图并对整数数组进行排序。