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。现在您可以使用计数排序对其进行两次排序，一次在 x1 上，一次在 x2 上，从而产生排序后的数组。

编辑：正如下面提到的其他人，像这样单独对每个“数字”进行排序称为基数排序。使用计数排序对每个数字进行排序需要 O(N) 时间和 O(N) 空间（在这种特殊情况下）。由于我们准确地重复了两次，因此总运行时间为 O(N)。

Answer 2

是的，你可以，使用N个桶和两次通过的基数排序。基本上，您将数字视为以N为底的 2 位数字。

Answer 3

O(n)可以使用基数排序及时对具有明确定义的最大值的任何整数数组进行排序。您遇到的任何整数列表都可能是这种情况。例如，如果您正在对任意精度整数列表进行排序，那将是不正确的。但是所有 C 整数类型都有明确定义的固定范围。