线性时间排序？

Question

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

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

Answer 1

也看看相关的排序：pigeonhole sort或counting sort，以及Pukku提到的radix sort。

Answer 2

看一看radix sort。

Answer 3

一组有限范围的数字可以用RANGE位的位图表示。 在这种情况下，一个500MB的位图，所以对于除了巨大列表之外的任何东西，使用基数排序会更好。当你遇到数字k时，设置位图[k] = 1。单遍历列表O（N）。

Answer 4

这是非常简单的，如果n = 2和编号是唯一的：

• 构建比特的阵列（2^31-1位=>〜256MB）。将它们初始化为零。
• 读取输入，对于您看到的每个值，将阵列中的相应位设置为1.
• 扫描阵列，为每个位设置，输出相应的值。

复杂性=> O（2N）

否则，使用基数排序：

复杂性=> O（KN）（希望）

Answer 5

wikipedia示出了相当多的不同的排序算法及其复杂性。你可能想要检查它们

Answer 6

当人们说“排序算法”时，他们经常指的是“比较排序算法”，这是任何算法，只能依赖于能够问“这个东西是大于还是小于”。所以如果你仅限于询问关于数据的这个问题，那么你永远不会得到超过n * log（n）（这是对数据集的n个阶乘可能排序进行log（n）搜索的结果） 。

如果您可以摆脱“比较排序”的限制并询问关于某个数据的更复杂问题，例如“这个数据的基数是多少”，那么您可以使用任意数量的线性时间排序算法，他们只需要更多的内存。

这是一个时间空间的折衷。 Comparason排序很少或没有ram，并在N * log（n）时间运行。基数排序（例如）在O（n）时间和O（log（基数））内存中运行。

Answer 7

一样ALGO是可能的：

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

它单独用于线性复杂性可能算法中，但它具有复杂度O（K * N）由RAM（N - 数的数组元素中，k - 元素的LEN）

Answer 8

将数字看作三位数字，其中每个数字的范围从0到n-1。用基数排序将这些数字排序。对于每一位数字都有一个调用计数排序的函数，这个函数需要Theta（n + n）时间，所以总运行时间对应于Theta（n）。