有O(n)整数排序算法吗?

对 Radix Sort 和 Counting Sort 是 O(N) . 它们不是以比较为基础的分类,事实证明它们是有区别的 Ω(N log N) 下限。

O(kN) 哪里 k 要排序的值中的位数。计数排序为 O(N + k) K 要排序的数字的范围。

有一些特定的应用程序 K 在实际应用中,基数排序和计数排序都表现出线性时间性能。

然而, counting sort 和 radix sort 与输入大小成线性比例-因为它们不是比较排序,所以它们利用了输入的固定结构。

计数排序: http://en.wikipedia.org/wiki/Counting_sort 如果你的整数很小。 基数排序,如果您有较大的数字(这基本上是计数排序的推广,或更大的数字优化,如果您愿意): http://en.wikipedia.org/wiki/Radix_sort

还有桶排序: http://en.wikipedia.org/wiki/Bucket_sort

Abacus (Bead) Sort 作为另一个有趣的线性时间排序算法。

这些基于硬件的排序算法:

A Comparison-Free Sorting Algorithm
Sorting Binary Numbers in Hardware - A Novel Algorithm and its Implementation

Laser Domino Sorting Algorithm -我做的一个基于计数排序的思维实验,目的是实现 O(n) 计算排序的时间复杂性 O(n + k) .

再加一点细节——实际上到目前为止最好的排序算法不是O(n),而是O(n)√(logn)预期时间。

您可以在中查看有关此算法的更多详细信息 Yijie Han & Mikkel Thorup 's FOCS '02 paper .