algorithm - 在 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)。
• 遍历每个桶，并对桶中的每个元素执行基数排序。

Answer 2

我觉得你运气不好。基数排序是 O(k*n)，其中 k 是位数。在您的情况下，k = log(n^2)，导致 O(n*log(n))。