基数排序
基数排序是一种线性排序,分为distribute(分配)和collect(回收)两个阶段。
算法需要:长度为10的队列。
每一轮分配,按照radix(基数)分别进入相应队列
例如待排序列为14,22,41,32,25,65,57
第一趟分配按照个位入队列
则每个队列为:
0号:空
1号:41
2号:22,,32
3号:空
4号:14
5号:25,65
6号:空
7号:57
8号:空
9号:空
回收阶段,将队列中数据依次回收
回收后:41,22,32,14,25,65,57
第二趟分配按照十位分配
0号:空
1号:14
2号:22,,25
3号:32
4号:41
5号:57
6号:65
7号:空
8号:空
9号:空
再次回收即已全部排序:14,22,25,32,41,57,65
注意的是分配与回收的总趟数由待排序列中最大数的位数决定
以下为代码:
[html]
public static void radixSort(int []arr,int d)
{
int power=1;
LinkedQueue[] digitQueue=new LinkedQueue[10];
for(int i=0;i<10;i++)
digitQueue[i]=new LinkedQueue();
for(int i=0;i
{
distribute(arr,digitQueue,power);
collect(digitQueue,arr);
power*=10;
}
}
private static void distribute(int[]arr,LinkedQueue[]digitQueue,int power)
{
for(int i=0;i
{
digitQueue[arr[i]/power%10].push(arr[i]);
}
}
private static void collect(LinkedQueue[]digitQueue,int[]arr)
{
int i=0;
for(int digit=0;digit<10;digit++)
{
while(!digitQueue[digit].isEmpty())
{
arr[i]=(Integer)digitQueue[digit].pop();
i++;
}
}
}
补充:软件开发 , Java ,