Java实现基数排序

????在众多的排序方法中基数排序比较特殊，它是一种不需要进行关键字之间比较的排序方法，利用多关键字的划分，逐渐将待排序列排好序。

举个例子：

现在有数组：278，109，63,930,589,184,505,269,8,83

第一次根据各位数将数组划分为10个队列(当然其中的某些队列可能不含有元素)

0:930

1:

2:

3:63,83

4:184

5:505

6：

7:

8:278,8

9:109,589,269

然后收集成序列：

930,63,83,184,505，278,8,109,589,269

在进行第二次分组：

0:505,8,109

1:

2:

3:930

4:

5:

6：63,269

7:278

8:83,184，589

9:

第二次收集：

505,8,109，930，63,269，278，83,184，589

第三次分配：

0:8,63,83

1:109,184

2:278,269

3:

4:

5:505,589

6:

7:

8:

9:930

最后得到序列：

8,63,83,109,184，269,278,505,589,930

完成排序！

基数排序其实是利用多关键字先达到局部有序，再调整达到全局有序。

public static void radixSort(int[] array){//首先确定排序的趟数;int max=array[0];for(int i=1;i<array.length;i++){if(array[i]>max){max=array[i];}}int time=0;//判断位数;while(max>0){max/=10;time++;}//建立10个队列;LinkQueue<Integer>[] queue=new LinkQueue[10];for(int i=0;i<10;i++){queue[i]=new LinkQueue<Integer>();}//进行time次分配和收集;for(int i=0;i<time;i++){    //分配数组元素;for(int j=0;j<array.length;j++){//得到数字的第time+1位数;queue[array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i)].enQueue(array[j]);}int count=0;//元素计数器;//收集队列元素;for(int k=0;k<10;k++){while(queue[k].size()>0){array[count]=(Integer) queue[k].deQueue().getElement();count++;}}}}

?如果待排序列的关键字不是自然数，我们当然可以对其进行转化，然后利用类似的方式排序。