排序算法Java实现（基数排序）

 1 package sorting;
 2 
 3 /**
 4  * 基数排序
 5  * 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂
 6  * d为位数,r为分配后链表的个数
 7  * @author zeng
 8  *
 9  */
10 public class JishuPaixu {
11 
12     public static int getNumInPos(int num, int pos) {
13         int tmp = 1;
14         for (int i = 0; i < pos - 1; i++) {
15             tmp *= 10;
16         }
17         return (num / tmp) % 10;
18     }
19 
20     public static int getMaxWeishu(int[] b) {
21         int max = b[0];
22         for (int i = 0; i < b.length; i++) {
23             if (b[i] > max)
24                 max = b[i];
25         }
26         int tmp = 1, i = 1;
27         while (true) {
28             tmp *= 10;
29             if (max / tmp != 0) {
30                 i++;
31             } else
32                 break;
33         }
34         return i;
35     }
36 
37     public static int[] jishupaixu(int[] a, int d) {
38 
39         int[][] array = new int[10][a.length + 1];
40         for (int i = 0; i < 10; i++) {
41             array[i][0] = 0;// array[i][0]记录第i行数据的个数
42         }
43         for (int pos = 0; pos < d; pos++) {
44             System.out.println("start fenpei");
45             for (int i = 0; i < a.length; i++) {// 分配过程
46                 int num = getNumInPos(a[i], pos + 1);
47                 int index = ++array[num][0];
48                 System.out.println("a[" + i + "]-->" + "array[" + num + "]["
49                         + index + "]");
50                 array[num][index] = a[i];
51             }
52             System.out.println("start shouji");
53             for (int i = 0, j = 0; i < 10; i++) {// 收集过程
54                 for (int k = 1; k <= array[i][0]; k++) {
55                     System.out.println("a[" + j + "]=" + "array[" + i + "]["
56                             + k + "]");
57                     a[j++] = array[i][k];
58                 }
59                 array[i][0] = 0;// 复位，下一个pos时还需使用
60             }
61         }
62 
63         return a;
64     }
65 
66     public static void main(String[] args) {
67         int[] b = { 49, 38, 65, 197, 76, 213, 27, 50 };
68         jishupaixu(b, getMaxWeishu(b));
69         for (int i : b)
70             System.out.print(i + " ");
71 
72     }
73 }