在O(n)中对[0,n ^ 2 - 1]之间的n个数进行排序？

Question

可能重复:
长度为N的数组可以包含值1,2,3 ... N ^ 2.是否有可能在O(n)时间内排序？

给定n范围内的数字[0,n^2 -1]我们如何在O(n)运行时间对它们进行排序？

我有一种感觉,解决方案涉及radix sort,但我仍然缺少一些东西.

该n数字是整数.

有任何想法吗 ？

备注:不是作业!

问候

Answer 1

实际时间将取决于您拥有的数据的分布，但我会执行以下操作：

• 制作n个桶。
• 遍历每个数字并将值为 i 的元素放入桶 sqrt(i) 中。
• 遍历每个桶，并对桶中的每个元素进行基数排序。