上周，我偶然发现了这篇论文，其中作者在第二页提到：
请注意，这会产生整数边权重的线性运行时间。
第三页也一样：
这会产生整数边权重的线性运行时间和基于比较的排序的 O(m log n) 时间。
在第 8 页：
特别是，使用快速整数排序可能会大大提高 GPA。
这是否意味着对于整数值在特殊情况下存在 O(n) 排序算法？或者这是图论的一个专业？
PS：
参考文献 [3] 可能会有所帮助，因为在第一页上他们说：
对[..]图类进行了进一步改进，例如整数边权重[3]、[...]
，但我无法访问任何科学期刊。
The last week I stumbled over this paper where the authors mention on the second page:
Note that this yields a linear running time for integer edge weights.
The same on the third page:
This yields a linear running time for integer edge weights and O(m log n) for comparison-based sorting.
And on the 8th page:
In particular, using fast integer sorting would probably accelerate GPA considerably.
Does this mean that there is a O(n) sorting algorithm under special circumstances for integer values? Or is this a specialty of graph theory?
PS:
It could be that reference [3] could be helpful because on the first page they say:
Further improvements have been achieved for [..] graph classes such as integer edge weights [3], [...]
but I didn't have access to any of the scientific journals.
发布评论
评论（7）
是的，基数排序和计数排序为
O(N)。它们不是基于比较的排序，已被证明具有Ω(N log N)下限。准确地说，基数排序是
O(kN)，其中k是要排序的值的位数。计数排序的复杂度是O(N + k)，其中k是要排序的数字的范围。在某些特定应用中，k 足够小，基数排序和计数排序在实践中都表现出线性时间性能。
Yes, Radix Sort and Counting Sort are
O(N). They are NOT comparison-based sorts, which have been proven to haveΩ(N log N)lower bound.To be precise, Radix Sort is
O(kN), wherekis the number of digits in the values to be sorted. Counting Sort isO(N + k), wherekis the range of the numbers to be sorted.There are specific applications where
kis small enough that both Radix Sort and Counting Sort exhibit linear-time performance in practice.比较排序的平均值必须至少为 Ω(n log n)。
但是，计数排序和基数排序随输入大小线性缩放 - 因为它们不是比较排序，所以它们利用输入的固定结构。
Comparison sorts must be at least Ω(n log n) on average.
However, counting sort and radix sort scale linearly with input size – because they are not comparison sorts, they exploit the fixed structure of the inputs.
计数排序：http://en.wikipedia.org/wiki/Counting_sort 如果你的整数相当小的。
如果您有更大的数字，则进行基数排序（这基本上是计数排序的概括，或者如果您愿意的话，可以对更大的数字进行优化）： http://en.wikipedia.org/wiki/Radix_sort
还有桶排序：http://en.wikipedia.org/wiki/Bucket_sort
Counting sort: http://en.wikipedia.org/wiki/Counting_sort if your integers are fairly small.
Radix sort if you have bigger numbers (this is basically a generalization of counting sort, or an optimization for bigger numbers if you will): http://en.wikipedia.org/wiki/Radix_sort
There is also bucket sort: http://en.wikipedia.org/wiki/Bucket_sort
这些基于硬件的排序算法：
无比较排序算法
硬件中的二进制数排序 - 一种新颖的算法及其实现
激光多米诺排序算法 - 我基于意图计数排序的思想实验与计数排序的
O(n + k)相比，实现了O(n)时间复杂度。These hardware-based sorting algorithms:
A Comparison-Free Sorting Algorithm
Sorting Binary Numbers in Hardware - A Novel Algorithm and its Implementation
Laser Domino Sorting Algorithm - a thought experiment by me based on Counting Sort with an intention to achieve
O(n)time complexity over Counting Sort'sO(n + k).虽然不是很实用（主要是由于内存开销很大），但我想我会提到 算盘（珠子）排序 作为另一个有趣的线性时间排序算法。
While not very practical (mainly due to the large memory overhead), I thought I would mention Abacus (Bead) Sort as another interesting linear time sorting algorithm.
接受的答案不是有效的 O(n) 排序，因为它是 O(n+k) 排序算法。
你应该看看斯大林排序
the accepted answer is not a valid O(n) sort as far as it is a O(n+k) sorting algorithm.
You should have a look at the Stalin Sort
添加更多细节 - 实际上迄今为止最好的排序算法不是 O(n)，而是 O(n √(log log n)) 预期时间。
您可以在Yijie Han & 中查看有关该算法的更多详细信息。 Mikkel Thorup 的 FOCS '02 论文。
Adding a little more detail - Practically the best sorting algorithm till date is not O(n), but O(n √(log log n)) expected time.
You can check more details about this algorithm in Yijie Han & Mikkel Thorup's FOCS '02 paper.