长度为N的数组可以包含值1,2,3…N ^ 2。是否可以按O（n）时间排序？

如何解决长度为N的数组可以包含值1,2,3…N ^ 2。是否可以按O（n）时间排序？？

将每个整数写入基数N，即每个x可以表示为（x1，x2），其中x = 1 + x1 + x2 *N。现在，您可以使用计数排序对其进行两次排序，一次在x1上，一次在x2上，从而生成已排序的数组。

解决方法

给定长度为N的数组。它可以包含从1到N ^ 2（N平方）（包括两个端点）的值，这些值是整数。是否可以在O（N）时间对该数组进行排序？如果可能的话如何？

编辑：这不是家庭作业。