57

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

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

第三页也一样：

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

在第 8 页：

特别是，使用快速整数排序可能会大大加快 GPA。

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

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

[..] 图类（例如整数边权重 [3]、[...]

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

4

6 回答 6

89

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

准确地说，基数排序是O(kN)，其中k是要排序的值的位数。计数排序是O(N + k)，其中k是要排序的数字的范围。

有一些特定的应用程序k足够小，以至于基数排序和计数排序在实践中都表现出线性时间性能。

于 2010-02-28T19:30:50.013 回答
17

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

然而，计数排序和基数排序与输入大小成线性关系——因为它们不是比较排序，它们利用了输入的固定结构。

于 2010-02-28T19:32:14.643 回答
6

计数排序：http ://en.wikipedia.org/wiki/Counting_sort如果您的整数相当小。如果您有更大的数字，则基数排序（这基本上是计数排序的概括，或者如果您愿意，可以对更大的数字进行优化）：http ://en.wikipedia.org/wiki/Radix_sort

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

于 2010-02-28T19:34:16.540 回答
2

虽然不是很实用（主要是由于内存开销很大），但我想我会提到Abacus (Bead) Sort作为另一种有趣的线性时间排序算法。

于 2010-03-01T16:00:25.610 回答
2

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

一种硬件中二进制数排序的免比较排序算法
——一种新算法及其实现

Laser Domino Sorting Algorithm - 我基于计数排序的思想实验，旨在实现O(n)计数排序的时间复杂度O(n + k)。

于 2016-09-12T18:50:14.540 回答
0

添加更多细节 - 实际上，迄今为止最好的排序算法不是 O(n)，而是 O(n √(log log n)) 预期时间。

您可以在Yijie Han 和 Mikkel Thorup的 FOCS '02 论文中查看有关此算法的更多详细信息。

于 2017-09-17T00:52:32.387 回答