algorithm - 长度为 N 的数组可以包含值 1,2,3 ... N^2。是否可以在 O(n) 时间内排序？

Question

给定一个长度为 N 的数组。它可以包含从 1 到 N^2(N 的平方)范围内的值，包括两端值，值是整数。是否可以在 O(N) 时间内对这个数组进行排序？如果可能怎么办？

编辑:这不是作业。

Answer 1

以N为底写出每个整数，即每个x都可以表示为(x1, x2)，其中x = 1 + x1 + x2*N。现在您可以使用 counting sort 对它进行两次排序，一次在 x1 上，一次在 x2 上，生成排序数组。

编辑:正如下面提到的其他人，像这样分别对每个“数字”进行排序称为 radix sort .使用计数排序对每个数字进行排序需要 O(N) 时间和 O(N) 空间(在这种特殊情况下)。由于我们恰好重复两次，因此总运行时间为 O(N)。