算法思想：依次按個位、十位...來排序，每一個pos都有分配過程和收集過程，array[i][0]記錄第i行數據的個數。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
package sorting;/** * 基數排序 * 平均O(d(n+r)),最好O(d(n+r)),最壞O(d(n+r));空間復雜度O(n+r);穩定;較復雜 * d為位數,r為分配后鏈表的個數 * @author zeng * */public class RadixSort { //pos=1表示個位，pos=2表示十位 public static int getNumInPos(int num, int pos) { int tmp = 1; for (int i = 0; i < pos - 1; i++) { tmp *= 10; } return (num / tmp) % 10; } //求得最大位數d public static int getMaxWeishu(int[] a) { int max = a[0]; for (int i = 0; i < a.length; i++) { if (a[i] > max) max = a[i]; } int tmp = 1, d = 1; while (true) { tmp *= 10; if (max / tmp != 0) { d++; } else break; } return d; } public static void radixSort(int[] a, int d) { int[][] array = new int[10][a.length + 1]; for (int i = 0; i < 10; i++) { array[i][0] = 0; // array[i][0]記錄第i行數據的個數 } for (int pos = 1; pos <= d; pos++) { for (int i = 0; i < a.length; i++) { // 分配過程 int row = getNumInPos(a[i], pos); int col = ++array[row][0]; array[row][col] = a[i]; } for (int row = 0, i = 0; row < 10; row++) { // 收集過程 for (int col = 1; col <= array[row][0]; col++) { a[i++] = array[row][col]; } array[row][0] = 0; // 復位，下一個pos時還需使用 } } } public static void main(String[] args) { int[] a = { 49, 38, 65, 197, 76, 213, 27, 50 }; radixSort(a, getMaxWeishu(a)); for (int i : a) System.out.print(i + " "); }} |
關注一下運行結果：
總結
以上就是本文關于Java語言實現基數排序代碼分享的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他Java相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://www.cnblogs.com/zengzhihua/p/4456753.html
