Java语言实现基数排序代码分享

时间:2022-06-23 01:39:51

算法思想:依次按个位、十位...来排序,每一个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语言实现基数排序代码分享的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他Java相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://www.cnblogs.com/zengzhihua/p/4456753.html