黑马程序员技术交流社区

标题: 分享，Java基数排序的算法实现 [打印本页]

---

作者: heshiwei    时间: 2015-10-7 16:19
标题: 分享，Java基数排序的算法实现
（1）基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

1. import java.util.ArrayList;
   
2. import java.util.List;
   
3. 
   
4. public class radixSort {
   
5.     inta[]={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};
   
6.         public radixSort(){
   
7.            sort(a);
   
8.            for(inti=0;i<a.length;i++){
   
9.                           System.out.println(a[i]);
   
10.            }
    
11.     }               
    
12.         public  void sort(int[] array){  
    
13.            //首先确定排序的趟数;  
    
14.            int max=array[0];  
    
15.            for(inti=1;i<array.length;i++){  
    
16.                         if(array[i]>max){  
    
17.                           max=array[i];  
    
18.                         }  
    
19.            }  
    
20.            int time=0;  
    
21.            //判断位数;  
    
22.            while(max>0){  
    
23.                   max/=10;  
    
24.                    time++;  
    
25.            }  
    
26. 
    
27.                 //建立10个队列;  
    
28.            List<ArrayList> queue=newArrayList<ArrayList>();  
    
29.            for(int i=0;i<10;i++){  
    
30.                           ArrayList<Integer>queue1=new ArrayList<Integer>();
    
31.                    queue.add(queue1);  
    
32.            }  
    
33. 
    
34.            //进行time次分配和收集;  
    
35.            for(int i=0;i<time;i++){  
    
36.                    //分配数组元素;  
    
37.                   for(intj=0;j<array.length;j++){  
    
38.                            //得到数字的第time+1位数;
    
39.                                  int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
    
40.                                  ArrayList<Integer>queue2=queue.get(x);
    
41.                                  queue2.add(array[j]);
    
42.                                  queue.set(x, queue2);
    
43.                   }
    
44.                   int count=0;//元素计数器;  
    
45.                   //收集队列元素;  
    
46.                   for(int k=0;k<10;k++){
    
47.                            while(queue.get(k).size()>0){
    
48.                                    ArrayList<Integer>queue3=queue.get(k);
    
49.                                    array[count]=queue3.get(0);  
    
50.                                    queue3.remove(0);
    
51.                                    count++;
    
52.                            }
    
53.                   }  
    
54.            }            
    
55.         }
    
56. }

复制代码

1347009583_9101.jpg (131.14 KB, 下载次数: 5)

下载附件

2015-10-7 16:19 上传

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2