线性时间sorting？
给定一个在[0..n ^ 3-1]范围内的n个整数的input集合，提供一个线性时间sortingalgorithm。
这是我在星期四对testing的评论，我不知道如何解决这个问题。
也请看相关的sorting：Pukku提到的sorting或计数sorting ，以及基数sorting 。
看看基数sorting 。
当人们说“sortingalgorithm”时，他们经常提到的是“比较sortingalgorithm”，这是任何一种algorithm，只能依赖于“比这更大还是更小”的问题。 所以如果你只限于问这个关于数据的问题，那么你将永远不会超过n * log（n）（这是对数据集的n个阶乘可能sorting进行log（n）search的结果） 。
如果你可以逃避“比较sorting”的限制，并提出一个更复杂的问题，例如“这个数据的基数是多less”，那么你可以提出任意数量的线性时间sortingalgorithm，他们只是需要更多的记忆。
这是一个时间空间的折衷。 比较sorting很less或没有RAM，并运行在N * log（n）时间。 基数sorting（例如）在O（n）时间和O（log（基数））内存中运行。
维基百科显示了很多不同的sortingalgorithm及其复杂性。 你可能想检查出来
这非常简单，如果n = 2并且数字是唯一的：
- 构build一个位数组（2 ^ 31-1位=>〜256MB）。 将它们初始化为零。
- 读取input，对于您看到的每个值，将数组中的相应位设置为1。
- 扫描arrays，为每个位设置，输出相应的值。
复杂性=> O（2n）
否则，使用基数sorting：
复杂性=> O（kn）（希望）
将数字看作三位数字，其中每个数字的范围从0到n-1。 用基数sorting来sorting这些数字。 对于每个数字都有一个调用计数sorting的函数，这个函数正在使用Theta（n + n）时间，所以总运行时间对应于Theta（n）。
一组有限范围的数字可以用RANGE位的位图表示。 在这种情况下，一个500MB的位图，所以除了巨大的列表，你最好用基数sorting。 当你遇到数字k，设置位图[k] = 1。单遍历列表，O（N）。
相同的algorithm是可能的：
M;// unsorted array lngth; //number items of M for(int i=0; i < lngth; i++)sorted[M[i]];
它是线性复杂度的唯一可能algorithm，但是它的复杂度为O（k * N），即ram（N数组元素，k元素的len）
