算法思想:依次按个位、十位...来排序,每一个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