24

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

这是我星期四测试的评论，我不知道如何解决这个问题。

4

8 回答 8

24

还要看看相关的排序：鸽子排序或计数排序，以及Pukku 提到的基数排序。

于 2009-04-14T22:29:39.153 回答
23

看看基数排序。

于 2009-04-14T22:26:22.390 回答
12

当人们说“排序算法”时，他们通常指的是“比较排序算法”，这是任何仅取决于能够询问“这个东西比那个更大还是更小”的算法。因此，如果您仅限于询问有关数据的这一问题，那么您将永远不会得到超过 n*log(n) （这是对数据集的 n 阶乘可能排序进行 log(n) 搜索的结果） .

如果您可以摆脱“比较排序”的约束并针对一段数据提出更复杂的问题，例如“此数据的基数为 10 基数是什么”，那么您可以提出任意数量的线性时间排序算法，他们只是占用更多的内存。

这是一个时空权衡。比较排序需要很少或不需要 ram，并在 N*log(n) 时间内运行。基数排序（例如）在 O(n) 时间和 O(log(radix)) 内存中运行。

于 2009-04-14T23:46:16.580 回答
3

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

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

复杂度 => O(2n)

否则，使用基数排序：

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

于 2009-04-14T22:35:25.877 回答
3

维基百科展示了许多不同的排序算法及其复杂性。你可能想检查一下

于 2009-04-14T22:35:42.617 回答
2

一组有限范围的数字可以由 RANGE 位的位图表示。在这种情况下，一个 500mb 的位图，所以对于除了巨大的列表之外的任何东西，你最好使用 Radix Sort。当你遇到数字 k 时，设置 bitmap[k] = 1。单次遍历列表，O(N)。

于 2009-04-14T22:33:23.887 回答
2

将数字视为三位数字，其中每个数字的范围从 0 到 n-1。使用基数排序对这些数字进行排序。对于每个数字，都会调用计数排序，它占用 Theta(n+n) 时间，因此总运行时间对应于 Theta(n)。

于 2012-11-14T17:37:01.827 回答
-2

类似的算法是可能的：

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

它是线性复杂度的唯一可能算法，但它的复杂度为 O(k*N) by ram（N - 数组元素，k - 元素的长度）

于 2009-04-15T00:06:21.510 回答