是否有 O(n) 整数排序算法? [英] Is there an O(n) integer sorting algorithm?

问题描述

上周我偶然发现了这篇论文 作者在第二页提到的地方:

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.

第三页相同:

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

This yields a linear running time for integer edge weights and O(m log n) for comparison-based sorting.

在第 8 页:

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

In particular, using fast integer sorting would probably accelerate GPA considerably.

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

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?

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

PS:
It could be that reference [3] could be helpful because on the first page they say:

已对 [..] 图类实现了进一步改进，例如整数边权重 [3]、[...]

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.

推荐答案

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

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.

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

To be precise, Radix Sort is O(kN), where k is the number of digits in the values to be sorted. Counting Sort is O(N + k), where k is the range of the numbers to be sorted.

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

There are specific applications where k is small enough that both Radix Sort and Counting Sort exhibit linear-time performance in practice.

这篇关于是否有 O(n) 整数排序算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！