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

Question

可能重复：
一个长度为N的数组可以包含1、2、3...N^2的值。有可能在O(n)时间内进行排序吗？

给定n个数字，范围为[0,n^2 -1]，如何在O（n）的时间内对它们进行排序？

我感觉解决方案涉及到基数排序，但我还缺少一些东西。

n个数字是整数。

有什么想法吗？

备注：不是作业！

问候

- JAN

---

有没有空间限制？ - biziclop

@Wug 这就是我想到的解决方案，但这是否意味着您必须遍历数组以收集结果，这是O(n^2)吗？ - biziclop

是的，这是一个问题。如果你处理大量数字，那么它会更好，因为会有较少的空白空间。没有通用算法可以在小于N*log(N)的时间内对事物进行排序，所以除非你处理的是可以更有效地处理的非常特定的情况，否则你就陷入了困境。 - Wug

你预计 n 会变得多大？似乎 n^2 很快就会超出大多数编程语言的正常 int 范围，除非 n 很小。 - mbeckish

另一个问题：你怎么知道这是可能的？ - biziclop

Answer 1

我认为你运气不太好。 基数排序的时间复杂度是O(k*n)，其中k是数字的位数。 在你的情况下，k = log(n^2)，所以时间复杂度是O(n*log(n))。

- mbeckish

---

存在一个O(n)的算法，参见https://dev59.com/Q1LTa4cB1Zd3GeqPWw_G。 - sdcvvc

@sdcwc - 如果您有一个O(n)的解决方案，那么请将其发布为答案，而不仅仅在评论中声称其存在。关于您提供的链接，我认为只有在数字的最大位数受到限制（例如32位或64位整数）时才是O(n)。这正确吗？ - mbeckish

在RAM模型中，对于字长整数的操作是O(1)。例如，二分搜索是O(log n) [如果计算位操作，则不是O(log^2 n)]。我投票将其关闭为重复内容。 - sdcvvc

“将k写成N进制数”不应该是一个O(logN)的操作吗？ - biziclop

@biziclop：这是位复杂度。在RAM模型中，它是O(1)。例如，在二分查找中的每一步计算(L+R)/2，但在分析中，假定加法需要在O(1)时间内完成。 - sdcvvc

Answer 2

实际时间取决于您的数据分布情况，但我会按照以下步骤进行：

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

- Kirby

---

每个桶的范围将是顺序N（sqrt（N ^ 2-1））。 基数排序需要时间O（R N），其中R是位数，在这种情况下将为lg N。 在最坏的情况下，所有元素都会落入同一个桶中，因此最后一步仍然需要O（N lg N）的时间。 - MWB

同意，最坏情况仍然很糟糕。不过，许多流行的算法（例如快速排序）在最坏情况下仍然表现不佳，这就是为什么它在很大程度上取决于数据分布。如果范围内的数据均匀分布，每个桶只有一个元素，并且排序完成时间复杂度为O(n)。 - Kirby