有没有一个O（n）整数sortingalgorithm？
上周我偶然发现了作者在第二页上提到的这篇文章 ：
请注意，这会产生整数边权重的线性运行时间。
第三页也一样：
这对于整数边的权重产生线性运行时间，对于基于比较的sorting产生O（m log n）。
并在第8页：
特别是使用快速整数sorting可能会大大加速GPA。
这是否意味着在特殊情况下有整数值的O（n）sortingalgorithm？ 或者这是图论的一个特点？
PS：
可能参考文献[3]可能会有帮助，因为在第一页他们说：
graphics类的整体边权重[3]，[…]
但我没有任何科学期刊。
是的，基数sorting和计数sorting是O(N) 。 它们不是基于比较的sorting，已经被certificate具有Ω(N log N)下限。
准确地说，基数sorting是O(kN) ，其中k是要sorting的值中的位数。 计数sorting是O(N + k) ，其中k是要sorting的数字的范围。
有一些具体的应用，其中k足够小，基数sorting和计数sorting在实践中performance出线性时间performance。
比较sorting的平均值必须至less为Ω（n log n）。
然而， 计数sorting和基数sorting与input大小成线性比例 – 因为它们不是比较sorting，它们利用input的固定结构。
计数sorting： http : //en.wikipedia.org/wiki/Counting_sort如果你的整数是相当小的。 基数sorting，如果你有更大的数字（这基本上是计数sorting的一般化，或如果你愿意更大的数字优化）： http : //en.wikipedia.org/wiki/Radix_sort
还有桶sorting： http : //en.wikipedia.org/wiki/Bucket_sort
虽然不是很实用（主要是由于大的内存开销），但我认为我会提到Abacus（Bead）Sort作为另一个有趣的线性时间sortingalgorithm。
这些基于硬件的sortingalgorithm：
无比较sortingalgorithm
硬件sorting二进制数 – 一种新algorithm及其实现
激光多米诺骨牌sortingalgorithm – 一个基于Countingsorting的思想实验，目的是实现O(n)时间复杂度超过Counting Sort的O(n + k) 。
添加更多的细节 – 实际上到目前为止，最好的sortingalgorithm不是O（n），而是0（n \ sqrt {\ log \ log n}）。
您可以在论文中查看有关此algorithm的更多详细信息： http ：//dl.acm.org/citation.cfm？id = 652131
