基数排序
将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成了一个有序序列。
算法实现:
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。 1 public class radixSort { 2 int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51}; 3 public radixSort(){ 4 sort(a); 5 for(inti=0;i<a.length;i++){ 6 System.out.println(a[i]); 7 } 8 } 9 public void sort(int[] array){ 10 //首先确定排序的趟数;
11 int max=array[0]; 12 for(inti=1;i<array.length;i++){ 13 if(array[i]>max){ 14 max=array[i]; 15 } 16 } 17 int time=0; 18 //判断位数;
19 while(max>0){ 20 max/=10; 21 time++; 22 } 23 //建立 10 个队列;
24 List<ArrayList> queue=newArrayList<ArrayList>(); 25 for(int i=0;i<10;i++){ 26 ArrayList<Integer>queue1=new ArrayList<Integer>( ); 27 queue.add(queue1); 28 } 29 //进行 time 次分配和收集;
30 for(int i=0;i<time;i++){ 31 //分配数组元素;
32 for(intj=0;j<array.length;j++){ 33 //得到数字的第 time+1 位数;
34 int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i); 35 ArrayList<Integer>queue2=queue.get(x); 36 queue2.add(array[j]); 37 queue.set(x, queue2); 38 } 39 int count=0;//元素计数器; 40 //收集队列元素;
41 for(int k=0;k<10;k++){ 42 while(queue.get(k).size()>0){ 43 ArrayList<Integer>queue3=queue.get(k); 44 array[count]=queue3.get(0); 45 queue3.remove(0); 46 count++; 47 } 48 } 49 } 50 } 51 }
更多精彩