写过的代码：基数排序

主要的类：

View Code

  1 //基数排序
  2 
  3 import java.util.*;
  4 
  5 public class RadixSort3 {
  6     // 数据
  7     /*
  8      * HashMap<Integer,LinkedList<Integer>> map = new
  9      * HashMap<Integer,LinkedList<Integer>>() ; LinkedList<Integer> list0 = new
 10      * LinkedList<Integer>() ; LinkedList<Integer> list1 = new
 11      * LinkedList<Integer>() ; LinkedList<Integer> list2 = new
 12      * LinkedList<Integer>() ; LinkedList<Integer> list3 = new
 13      * LinkedList<Integer>() ; LinkedList<Integer> list4 = new
 14      * LinkedList<Integer>() ; LinkedList<Integer> list5 = new
 15      * LinkedList<Integer>() ; LinkedList<Integer> list6 = new
 16      * LinkedList<Integer>() ; LinkedList<Integer> list7 = new
 17      * LinkedList<Integer>() ; LinkedList<Integer> list8 = new
 18      * LinkedList<Integer>() ; LinkedList<Integer> list9 = new
 19      * LinkedList<Integer>() ;
 20      */
 21     HashMap<Integer, FirstLastList> map = new HashMap<Integer, FirstLastList>();
 22     FirstLastList[] list = new FirstLastList[10];
 23 
 24     // 方法
 25     // --------------------------------------------------
 26     public RadixSort3() {
 27         /*
 28          * map.put(0,list0) ; map.put(1,list1) ; map.put(2,list2) ;
 29          * map.put(3,list3) ; map.put(4,list4) ; map.put(5,list5) ;
 30          * map.put(6,list6) ; map.put(7,list7) ; map.put(8,list8) ;
 31          * map.put(9,list9) ;
 32          */
 33         // 初始化链表
 34         for (int i = 0; i < 10; i++)
 35             list[i] = new FirstLastList();
 36         // 将链表插入到映射中
 37         for (int i = 0; i < 10; i++)
 38             map.put(i, list[i]);
 39 
 40     }
 41 
 42     // --------------------------------------------------
 43     // 基数排序
 44     public void radixSort(long[] array) {
 45         int digit;// 记录当前的位数
 46         int figure;// 记录当前位数所指定的数字
 47         int maxSize = getMaxSize(array);// 存储数组中最大数的位数
 48         for (digit = 1; digit <= maxSize; digit++) {
 49             // 把各个数插入到符合的链表
 50             for (int index = 0; index < array.length; index++) {
 51                 figure = getDigit(digit, array[index]);
 52                 putIntoList(figure, array[index]);
 53             }
 54             // 把链表中的值返回到数组中
 55             returnIntoArray(array);
 56         }
 57     }
 58 
 59     // --------------------------------------------------
 60     // 显示数组
 61     public void displayArray(long[] array) {
 62         for (int index = 0; index < array.length; index++)
 63             System.out.print(array[index] + " ");
 64         System.out.println();
 65     }
 66 
 67     // ---------------------------------------
 68     // 返回各位数
 69     private int getDigit(int digit, long number) {
 70         /*
 71          * 假设最大位数为5位 switch(digit) { case 1:return ((int)(number%10)) ; case
 72          * 2:return ((int)(number/10)%10) ; case 3:return ((int)(number/100)%10)
 73          * ; case 4:return ((int)(number/1000)%10) ; case 5:return
 74          * ((int)(number/10000)) ; }
 75          */
 76         for (int k = 1; k < digit; k++)
 77             number = number / 10;
 78         return (int) number % 10;
 79     }
 80 
 81     // -----------------------------------------
 82     // 把数据插入到链表中
 83     private void putIntoList(int figure, long number) {
 84         switch (figure) {
 85         case 0:
 86             list[0].insertLast(number);
 87             break;
 88         case 1:
 89             list[1].insertLast(number);
 90             break;
 91         case 2:
 92             list[2].insertLast(number);
 93             break;
 94         case 3:
 95             list[3].insertLast(number);
 96             break;
 97         case 4:
 98             list[4].insertLast(number);
 99             break;
100         case 5:
101             list[5].insertLast(number);
102             break;
103         case 6:
104             list[6].insertLast(number);
105             break;
106         case 7:
107             list[7].insertLast(number);
108             break;
109         case 8:
110             list[8].insertLast(number);
111             break;
112         case 9:
113             list[9].insertLast(number);
114             break;
115         }
116     }
117 
118     // ----------------------------------------------------
119     // 将数据返回到数组中
120     public void returnIntoArray(long[] array) {
121         // LinkedList<Integer> list ;
122         FirstLastList list;
123         int flag = -1;
124         for (int i = 0; i < 10; i++) {
125             list = (map.get(i));
126             // Object data = list.pollFirst() ;
127 
128             while (!list.isEmpty()) {
129                 array[++flag] = list.deleteFirst();
130             }
131         }
132     }
133 
134     // ----------------------------------------------------
135     // 返回数组中最大的那个值的位数
136     public int getMaxSize(long[] array) {
137         // 找到最大数
138         long max = array[0];
139         for (int i = 1; i < array.length; i++) {
140             if (max < array[i])
141                 max = array[i];
142         }
143         /*
144          * if(max>10000&&max<100000) return 5 ; else if(max>1000) return 4 ;
145          * else if(max>100) return 3 ; else return (max>10?2:1) ;
146          */
147         int count = 0;
148         while (max != 0) {
149             max = max / 10;
150             count++;
151         }
152         return count;
153     }
154 }

辅助的类：

View Code

 1 class FirstLastList {
 2     private Link first; // ref to first link
 3     private Link last; // ref to last link
 4     // -------------------------------------------------------------
 5 
 6     public FirstLastList() // constructor
 7     {
 8         first = null; // no links on list yet
 9         last = null;
10     }
11 
12     // -------------------------------------------------------------
13     public boolean isEmpty() // true if no links
14     {
15         return first == null;
16     }
17 
18     // -------------------------------------------------------------
19     public void insertFirst(long dd) // insert at front of list
20     {
21         Link newLink = new Link(dd); // make new link
22 
23         if (isEmpty()) // if empty list,
24             last = newLink; // newLink <-- last
25         newLink.next = first; // newLink --> old first
26         first = newLink; // first --> newLink
27     }
28 
29     // -------------------------------------------------------------
30     public void insertLast(long dd) // insert at end of list
31     {
32         Link newLink = new Link(dd); // make new link
33         if (isEmpty()) // if empty list,
34             first = newLink; // first --> newLink
35         else
36             last.next = newLink; // old last --> newLink
37         last = newLink; // newLink <-- last
38     }
39 
40     // -------------------------------------------------------------
41     public long deleteFirst() // delete first link
42     { // (assumes non-empty list)
43         long temp = first.dData;
44         if (first.next == null) // if only one item
45             last = null; // null <-- last
46         first = first.next; // first --> old next
47         return temp;
48     }
49 
50     // -------------------------------------------------------------
51     public void displayList() {
52         System.out.print("List (first-->last): ");
53         Link current = first; // start at beginning
54         while (current != null) // until end of list,
55         {
56             current.displayLink(); // print data
57             current = current.next; // move to next link
58         }
59         System.out.println("");
60     }
61     // -------------------------------------------------------------
62 } // end class FirstLastList

View Code

 1 class Link
 2 {
 3 public long dData;                 // data item
 4 public Link next;                  // next link in list
 5 //-------------------------------------------------------------
 6 public Link(long d)                // constructor
 7    { dData = d; }
 8 //-------------------------------------------------------------
 9 public void displayLink()          // display this link
10    { System.out.print(dData + " "); }
11 //-------------------------------------------------------------
12 }  // end class Link

测试类：

View Code

 1 //测试程序
 2 public class RadixSort3App
 3 {
 4   public static void main(String[] agrs)
 5   {
 6       RadixSort3 test = new RadixSort3() ;
 7       long[] array = new long[10];
 8       //int[] array = {412,240,35,532,305,430,124,1000,1234,98423,12345} ;
 9       //插入十个随机数
10       int value ;
11       for(int i=0 ; i<10;i++)
12       {
13           value = (int)(Math.random()*100000) ;
14           array[i] = value ;
15       }
16       System.out.println("排序前：") ;
17       test.displayArray(array) ;
18       test.radixSort(array) ;
19       System.out.println("排序后：") ;
20       test.displayArray(array) ;
21   }
22 }

View Code

 1 //测试大数据
 2 import java.util.* ;
 3 public class RadixSortApp2
 4 {
 5   public static void main(String[] agrs)
 6   {
 7       RadixSort3 test = new RadixSort3() ;
 8       long[] array ;
 9       int value ;
10       int maxSize = 10000 ;
11       System.out.println("【基数排序】") ;
12       System.out.println("数组大小——>时间(ms)") ;
13       while(maxSize<=100000)
14       {
15           array = new long[maxSize] ;
16           System.out.print(maxSize+"——>") ;
17           for(int i=0 ; i<maxSize ;i++)
18           {
19              value = (int)(Math.random()*100000) ;
20              array[i] = value ;
21           }
22           Date before = new Date() ;
23           test.radixSort(array) ;
24           Date after = new Date() ;
25           long time = after.getTime() - before.getTime() ;
26           System.out.println(time) ;
27           maxSize += 10000 ;
28       }
29   }
30 }