将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成了一个有序序列。

算法实现:

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 }
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄