按线性时间排序？

Question

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

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

Answer 1

只是需要注意的是，只有当您的键有固定的最大长度时，基数排序才是线性的...因为您有一个整数范围，那么是的，它可以是线性的，但情况并非总是如此。 (2认同)
n 个 d 位数字的范围在 [0, n^3 - 1] 中，则 d 位数字的数量为 3log(n)，算法将在 O(dn) => O(nlog(n) ）。基数排序不是线性解决方案。 (2认同)

Answer 2

另外看看相关的排序:鸽子排序或计数排序,以及Pukku提到的基数排序.

难道你不认为n ^ 3-1有点太大而无法使用计数排序？如果n = 100,你将有100 ^ 3的空间来排序.他需要更改整数的基数并使用Radix排序. (3认同)
如果 n 个 d 位数字的范围在 [0, n^3 - 1] 中，则 d 位数字的个数为 3log(n)，算法的运行时间为 O(dn) => O(nlog(n) ）。基数排序不是线性解决方案。此外，鸽子笼也不合适，因为元素的数量与可能的键的数量“大约相同”。 (2认同)

Answer 3

当人们说"排序算法"时,他们经常提到"比较排序算法",这是任何只依赖于能够问"这个比这个更大还是更小"的算法.因此,如果您仅限于询问有关数据的这一个问题,那么您将永远不会获得超过n*log(n)(这是对数据集的n个阶乘可能排序进行log(n)搜索的结果) .

如果你可以逃避"比较排序"的约束并询问关于一个数据的更复杂的问题,例如"这个数据的基数10基数是什么"那么你可以提出任意数量的线性时间排序算法,他们只是需要更多的记忆.

这是一个时间空间权衡.Comparason排序很少或没有ram并且在N*log(n)时间内运行.基数排序(例如)在O(n)时间和O(log(基数))内存中运行.