线性时间排序？[关闭]

Question

给定 [0..n^3-1] 范围内的 n 个整数的输入集，提供线性时间排序算法。

这是我周四测试的回顾，我不知道如何解决这个问题。

Answer 1

也看看相关的排序： 鸽巢排序 或者 计数排序, ， 也 基数排序 正如普库提到的。

Answer 2

看一看基数排序。

Answer 3

当人们说“排序算法”，他们往往指的是“比较排序算法”，这是任何算法，仅依赖于能够问“这东西比更大或更小”。所以，如果你只限于询问有关数据这一问题，那么你将永远不会得到比的n * log（n）的更多（这是做的log（n）搜索n的数据集的阶乘可能的排序结果） 。

如果你能逃脱“比较排序”的约束，并要求更复杂的问题，关于一个数据，比如“什么是基地10这个数据的基数”，那么你可以拿出任意数量的线性时间排序算法，他们只是需要更多的内存。

这是一个时间空间权衡。 Comparason排序需要很少或没有RAM和N *日志（n）时间内运行。基数排序（例如）运行在O（n）的时间和O（日志（基数））存储器。

Answer 4

维基示出了相当多的不同的排序算法及其复杂性。你可能要检查出来

Answer 5

这真的很简单，如果 n=2 并且数字是唯一的：

• 构造一个位数组（2^31-1 位 => ~256MB）。将它们初始化为零。
• 读取输入，对于您看到的每个值，将数组中的相应位设置为 1。
• 扫描数组，对于每个位组，输出相应的值。

复杂度 => O(2n)

否则，使用基数排序：

复杂度 => O(kn) （希望如此）

Answer 6

想的编号，其中每个数字范围从0到n-1三位数。排序这些数字与基数排序。每个数字有到计数排序其服用西塔（N + n）的时间，从而使总的运行时间对应于西塔（n）的

的呼叫

Answer 7

一组有限范围的数字可以由 RANGE 位的位图表示。在本例中，位图大小为 500mb，因此对于除大型列表之外的任何内容，最好使用基数排序。当遇到数字 k 时，设置 bitmap[k] = 1。单次遍历列表，O(N)。

Answer 8

一样ALGO是可能的：结果

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

这是单独为线性复杂性可能算法中，但它通过冲压具有复杂度O（K * N）（N - 数的数组元素中，k - 元素的LEN）