rid*_*hap 6 sorting algorithm radix-sort
给定一个长度为N的数组.它可以包含范围从1到N ^ 2(N平方)的值,包括值,值是整数.是否可以在O(N)时间内对此数组进行排序？如果可能怎么样？
编辑:这不是作业.
在基数N中写入每个整数,即每个x可以表示为(x1,x2),其中x = 1 + x1 + x2*N. 现在,您可以使用计数排序对其进行两次排序,一次在x1上,一次在x2上,从而生成排序数组.
| 归档时间： |
|
| 查看次数： |
3794 次 |
| 最近记录： |