基数排序

基数排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述

• 取得数组中的最大数，并取得位数；
• arr 为原始数组，从最低位开始取每个位组成 radix 数组；
• 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；

动图演示

实例

1. 代码实现

public class RadixTest {
    public static void main(String[] args) {
        int[] a = {13,25,1111,232,4454,79,86,98,61,447};
        System.out.println("初始值:");
        printArray(a);
        a= sort(a);
        System.out.println("\n排序后:");
        printArray(a);
    }
    
    public static int[] sort(int[] data) {
        int maxLength = getMaxLength(data);
        int[] temp = baseSort(data,0,maxLength);
        return temp;
    }
    
    private static int[] baseSort(int[] data,int i,int maxLength) {
        if(i >= maxLength) {
            return data;
        }
        
        int len = data.length;
        
        int[] count = new int[10];
        
        int[] temp = new int[len];
        
        for (int j = 0;j < temp.length;j++) {
            count[getNum(data[j],i)]++;
        } 
        
        for (int m = 1;m < count.length;m++) {
            count[m] = count[m - 1] + count[m];
        } 
        
        for(int n = temp.length - 1;n >= 0;n--) {
            int number = data[n];
            int a = getNum(number,i);
            temp[count[a] - 1] = number;
            count[a]--;
        }
        
        return baseSort(temp, i+1, maxLength);
    }
    
    /**
    * 获取一个数字第i位得数字,个位从0开始
    */
    private static int getNum(int num,int i) {
        for(int j = 0;j < i + 1;j++) {
            if (j == i) {
                num %= 10;
            } else {
                num /= 10;
            }
        }
        
        return num;
    }
    
    private static int getMaxLength(int[] a) {
        int maxLength = 0;
        for (int i = 0;i < a.length;i++) {
            if(maxLength < length(a[i])) {
                maxLength = length(a[i]);
            }
           
        } 
        
        return maxLength;
    }
    
    /**
    * 获取数组的长度
    */
    private static int length(int num) {
        return String.valueOf(num).length();
    }
    
    private static void printArray(int[] a) {
        for (int i = 0;i < a.length;i++) {
            System.out.print(a[i] + " ");
        } 
        System.out.println();
    }
}

2. 输出结果

   
   05.png