长度N的数组可以包含值1、2、3…N^2。能在O(n)时间内分类吗?

以N为基数写下每个整数,即每个x可以用x=1+x1+x2*N表示为(x1,x2)。现在可以用计数排序对它排序两次,一次在x1上,一次在x2上,从而得到排序的数组。

是的,你可以,用 radix sort 具有 N个 桶和两次传球。基本上,你把这些数字看作是两位数的基数 N .

可以对任何具有良好定义的最大值的整数数组进行排序。 O(n) 使用时间 radix sort . 这可能是您遇到的任何整数列表的情况。例如,如果对任意精度整数的列表进行排序,则不会为真。但是所有的C积分类型都有定义良好的固定范围。