长度为 N 的数组可以包含值 1,2,3 ... N^2。是否可以在 O(n) 时间内排序？
给定一个长度为 N 的数组。它可以包含范围从 1 到 N^2（N 平方）（包括这两个值）的值，值是整数。是否可以在 O(N) 时间内对这个数组进行排序？如果可以的话怎么办？
编辑：这不是作业。
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
将每个整数以 N 为基数写入，即每个 x 都可以表示为 (x1, x2)，其中 x = 1 + x1 + x2*N。现在，您可以使用 计数排序对其进行两次排序，一次在 x1 上，一次在 x2 上，结果是排序后的数组。
编辑：正如下面其他人提到的，像这样对每个“数字”单独排序被称为 基数排序。使用计数排序对每个数字进行排序需要 O(N) 时间和 O(N) 空间（在本例中）。由于我们正好重复两次，因此总运行时间为 O(N)。
Write each integer in base N, that is each x can be represented as (x1, x2) with x = 1 + x1 + x2*N. Now you can sort it twice with counting sort, once on x1 and once on x2, resulting in the sorted array.
EDIT: As others mentioned below, sorting on each 'digit' separately like this is is called a radix sort. Sorting on each digit with counting sort takes O(N) time and O(N) space (in this particular case). Since we repeat it exactly twice, this gives a total running time of O(N).
是的，您可以，使用 基数排序 和 N 个存储桶两趟。基本上，您将这些数字视为具有 2 位以 N 为基数的数字。
Yes, you can, using radix sort with N buckets and two passes. Basically, you treat the numbers as having 2 digits in base N.
可以使用 O(n) 时间内对具有明确定义的最大值的任何整数数组进行排序="nofollow">基数排序。对于您遇到的任何整数列表都可能出现这种情况。例如，如果您要对任意精度整数的列表进行排序，则事实并非如此。但所有 C 整数类型都有明确定义的固定范围。
It is possible to sort any array of integers with a well defined maximum value in
O(n)time using a radix sort. This is likely the case for any list of integers you encounter. For example if you were sorting a list of arbitrary precision integers it wouldn't be true. But all the C integral types have well-defined fixed ranges.