是否有O(n)整数排序算法？

Question

上周我偶然发现了这篇论文,作者在第二页提到:

请注意,这会产生整数边权重的线性运行时间.

第三页上的内容相同:

这产生整数边缘权重的线性运行时间和基于比较的排序的O(m log n).

在第8页:

特别是,使用快速整数排序可能会显着加速GPA.

这是否意味着在特殊情况下存在整数值的O(n)排序算法？或者这是图论的专长？

PS:
可能参考文献[3]可能会有所帮助,因为在第一页上他们说:

[...]图表类已经实现了进一步的改进,例如整数边权重[3],[...]

但是我无法访问任何科学期刊.

Answer 1

是的,基数排序和计数排序是O(N).它们不是基于比较的排序,已被证明具有?(N log N)下限.

确切地说,基数排序是O(kN),k要排序的值中的位数在哪里.计数排序是O(N + k),k要排序的数字的范围在哪里.

特定的应用程序k足够小,基数排序和计数排序在实践中表现出线性时间性能.

下限始终表示为Ω.说O下界没有语义含义.否则+1. (20认同)
@David"对于k个数字的n个键,基数排序的效率因此为O(kn).由于k通常在log n的数量级上,因此基数排序可能看起来并没有真正超过O(n log n)时间.最佳比较排序.*然而,最佳比较排序的O(n log n)时间***计算比较次数**,比较的最快时间是k.如果我们计算基本操作的数量,然后合并排序(或其他快速比较排序)在O(kn log n)时间执行." (4认同)
那只是语义.数字不必是基数10.我可以将它设置为256,这与你的参数基本相同. (3认同)
@polygenelubricants “因为 k 通常是 log n 的数量级”这是为什么？ (3认同)
如果整数的最大可能值小于或等于 n，它们只是“O(n)”——否则它们是“O(max_int)”，不是吗？ (2认同)
如果硬件足够宽，@polygenelubricants 整数比较不需要 k 时间。 (2认同)

Answer 2

比较排序平均必须至少为Ω(n log n).

但是,计算排序和基数排序与输入大小成线性关系 - 因为它们不是比较排序,它们利用输入的固定结构.

Answer 3

计数排序：如果您的整数非常小，请访问http://en.wikipedia.org/wiki/Counting_sort。如果您有更大的数字，则进行基数排序（这基本上是计数排序的概括，或者，如果有的话，这是对更大的数字的优化）：http : //en.wikipedia.org/wiki/Radix_sort