长度为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计数排序，一旦两次排序并一次在X 2，得到的排序后的数组英寸

Answer 2

是，可以使用基数排序与Ñ水桶和两遍。基本上，把这些数字作为具有在基体2个位数的Ñ

Answer 3

是可能的排序整数与一良好限定的最大值在时间O(n)使用基数排序任何数组。这可能是你遇到的任何整数列表的情况。例如，如果你是排序的任意精度的整数列表它不会是真实的。但所有的C整数类型具有明确固定的范围内。