如何排序(百万/十亿/…)整数?

如果你有这样一个问题,他们不会找答案的。他们想做的是看看你如何思考问题。你是直接跳进去,还是问关于项目需求的问题?

你最好问的一个问题是,“问题需要多好的解决方案?”也许存储在文件中的气泡式记录就足够了,但是你必须问。问一些问题,如果输入更改为64位数字,那么排序过程是否容易更新?询问程序员开发程序需要多长时间。

这些类型的问题告诉我,候选人是明智的,足以看到有更多的问题,而不仅仅是排序数字。

我希望他们在找你来扩大 internal sorting 和 external sorting . 显然人们不识字 Knuth 现在

AS aaaa bbbb 说,这要视情况而定。您将询问有关项目需求的问题。例如,如果他们想计算员工的年龄,您可能会使用 Counting sort ,我可以对内存中的数据进行排序。但当数据完全随机时,您可能会使用 external sorting . 例如,可以将源文件的数据分为不同的文件,每个文件都有一个唯一的范围(文件1从0-1米,文件2从1米+1-2米等等),然后对每个文件进行排序,最后将它们合并到一个新文件中。

这取决于它们存储在的数据结构。如果输入在链表中,基数排序比n-log-n排序在较小的问题大小上要好,因为它不需要分配任何临时内存,并且如果您能够负担得起在排序开始时分配临时缓冲区输入的大小,那么数组也是如此。这真的只是 错误的 当您有非常有限的额外存储空间并且您的输入在一个数组中时,选择(对于整数键)。

不管怎样,我希望交叉点远低于一百万。

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