高效的排序？

Question

我寻找这个问题的答案已经有一段时间了。“对一百万个32位整数进行排序的最有效方法是什么？”

我觉得快速排序在排序中是最有效的。平均运行时间为O(n*log )。(最坏情况为O(n²))..

但一些搜索结果表明，基数排序/合并排序对于排序百万个整数是有效的。

有什么建议吗？

Answer 1

Mergesort保证为O(n lg n)，但比快速排序具有更高的内存占用。

快速排序通常比合并排序运行得更快，但在某些情况下，它可能会降级为二次运行时间。

基数排序是O(n*r)，其中r是数字的长度。

要确定基数是否比您选择的lg-n方法更好，请执行以下操作：

n * r < n * lg (n)
divide by n on both sides
r < lg(n)

We know r is 32 bits

32 < lg(n)

for both sides, take 2^x

2^32 < 2^(lg(n)

2^32 < n

因此，如果n小于2^32 (40亿)，则使用lg-n算法。

就我个人而言，我会使用快速排序，如果有必要的话，我会对它进行混洗，以防止它降级。

Answer 2

如果您有足够的空间，也许可以尝试存储桶排序(http://en.wikipedia.org/wiki/Bucket_sort)。它效率更高，但需要额外的内存来存储数据。

Answer 3

基数更适合于大数，特别是当你知道这些数的范围时。

计算修复：

基数是O(kN)，其中k是最大数的位数。(实际上它是关于d*k*N的，其中d是数字基数，将使用的存储桶数...

Maxint = 4,294,967,296

32位:K= 32 / log(d)

基数10的基数：

d*k*n = 10*10*n < nlogn .... 100 < logn ... n > 2^100  

d*k*n = 2*32*n < nlogn .... 64 < logn ... n > 2^64

因此，对于32位数字，如果你有超过2^64的数字，n*k*N比nlogn更好

但是，如果您知道范围将达到1024，而不是MAXINT，例如：

MaxNumber = 1024

基数10的基数：

d*k*n = 10*4*n < nlogn .... 40 < logn ... n > 2^40 

d*k*n = 2*10*n < nlogn .... 20 < logn ... n > 2^20

因此，对于1024个以上的数字，如果您有超过2^20个数字，则n*k*N比nlogn更好

由于大O表示法在运行时间上丢弃了乘法常量，并且忽略了低输入大小的效率，因此它并不总是在实践中或对于实际大小的数据集显示最快的算法，但当输入大小变大时，该方法仍然非常有效地比较各种算法的可扩展性。