上周，我偶然发现了这篇论文，作者在第二页上提到：
注意，对于整数边缘权重，这将产生线性运行时间。
第三页相同：
对于整数边缘权重，这将产生线性运行时间；对于基于比较的排序，这将产生O（m log n）。
并在第8页上：
特别是，使用快速整数排序可能会大大提高GPA。
这是否意味着在特殊情况下对整数值有O（n）排序算法？还是这是图论的专长？
PS： 可能参考文献[3]可能会有所帮助，因为他们在首页上说：
对于[..]图形类，例如整数边缘权重[3]，[…]，已经实现了进一步的改进
但是我没有任何科学期刊。
是的，基数排序和计数排序是O(N)。它们不是基于比较的排序，已被证明具有Ω(N log N)较低的界限。
O(N)
Ω(N log N)
确切地说，基数排序是O(kN)，其中k是要排序的值中的位数。计数排序是O(N + k)，其中k要排序的数字范围。
O(kN)
k
O(N + k)
在某些特定的应用程序中，k小到足以使基数排序和计数排序在实践中都表现出线性时间性能。
