基数排序（Radix Sort）——java实现

关于基数排序的相关概念这里就不多说了，参考基数排序 。 觉得麻烦的看下面的内容：

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序的效率：

基数排序的时间复杂度是 O(k·n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n))，因为k的大小一般会受到 n 的影响。 以排序n个不同整数来举例，假定这些整数以B为底，这样每位数都有B个不同的数字，k就一定不小于log_B(n)。由于有B个不同的数字，所以就需要B个不同的桶，在每一轮比较的时候都需要平均n·log₂(B) 次比较来把整数放到合适的桶中去，所以就有：

• k 大于或等于 log_B(n)
• 每一轮(平均)需要 n·log₂(B) 次比较

所以，基数排序的平均时间T就是：

T ≥ log_B(n)·n·log₂(B) = log₂(n)·log_B(2)·n·log₂(B) = log₂(n)·n·log_B(2)·log₂(B) =n·log₂(n)

所以和比较排序相似，基数排序需要的比较次数：T ≥ n·log₂(n)。 故其时间复杂度为Ω(n·log₂(n)) = Ω(n·log n) 。

（以上内容摘自 基数排序-维基百科）

对RS= {43,21,60 ， 71 ， 54 ， 24 ， 97} ， 基数排序 （Radix Sort） 的一趟排序 ：

每个数对10取余数 ， 分别得到 ： 3 ， 1 ， 0 ， 1 ， 4 ， 4 ， 7 

整合新的数据到待排序集合，得到如下结果：

60,21,71,43,54,24

然后再对结果十位取余，直到最大位数n。这里n=2.

    public static void radixSort(int[] num) {
        if (isEmpty(num))
            return;
        int tmp = getMax(num);
        // get loop count
        int loop = 0;
        do {
            loop++;
        } while ((tmp = tmp / 10) > 0);
        int count = 1, k, lsd;
        int[][] bubble = new int[10][num.length];
        int[] order = new int[10];
        tmp = 1;
        while (count <= loop) {
            for (int i = 0; i < num.length; i++) {
                lsd = (num[i] / tmp) % 10;
                bubble[lsd][order[lsd]] = num[i];
                order[lsd]++;
            }
            k = 0;
            for (int i = 0; i < 10; i++) {
                if (order[i] != 0) {
                    for (int j = 0; j < order[i]; j++) {
                        num[k] = bubble[i][j];
                        k++;
                    }
                }
                order[i] = 0;
            }
            tmp *= 10;
            count++;
        }
    }

    private static int getMax(int[] num) {
        if (isEmpty(num)) {
            throw new IllegalArgumentException();
        }
        int max = num[0];
        for (int i = 1; i < num.length; i++) {
            if (max < num[i])
                max = num[i];
        }
        return max;
    }

    private static boolean isEmpty(int[] num) {
        return num == null || num.length == 0;
    }

10 , 表示十进制的各个数：0 ， 1 , 2 ， 3， 4， 5， 6, 7， 8， 9 。

基数排序（Radix Sort）——java实现,布布扣,bubuko.com

基数排序（Radix Sort）——java实现

原文：http://blog.csdn.net/sun_star1chen/article/details/20313167