是否有一个O（n）的整数排序算法？ [英] Is there an O(n) integer sorting algorithm?

问题描述

上周，我绊了<一href="http://www.pw.ethz.ch/people/research_group/mauej/personal/publications/MaueSanders2007.pdf">this纸其中作者提到的第二页上：

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.

第三页上是相同的：

这会产生一个线性的运行时间为整数边权和0（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?

PS：
这可能是参考文献[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日志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.

要为precise，基数排序是 0（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屋！