基数排序面试题

001什么是基数排序？

1）基数排序是对桶排序的一种改进，这种改进是让“桶排序”适合于更大的元素值集合的情况，而不是提高性能。它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。

2）算法图解

第一步，将所有待比较数值根据个位数的数值分别分配至编号0到9的桶中；

第二步，桶中数据根据先进先出的原则出来，收集完整的序列；

第三步，十位、百位....周而复始

002基数排序的代码实现？

//digit代表最大的数有几个十进制位
public static void radixSort(int[] arr, int L, int R, int digit) {
    //十进制数
    final int radix = 10;
    int i = 0, j = 0;
    // 有多少个数准备多少个辅助空间
    int[] bucket = new int[R - L + 1];
    for (int d = 1; d <= digit; d++) { // 有多少位就循环几次
        //十进制的数，创建长度为10的数组
        int[] count = new int[radix]; // count[0..9]
        for (i = L; i <= R; i++) {
            j = getDigit(arr[i], d);//获取该数的个位、十位、百位......上的数
            count[j]++;//获取数组中每个数每位分别是1、2、3....9数分别总共有几个
        }
        for (i = 1; i < radix; i++) {
            //获取数组中每个数每位分别是<=1、<=2、<=3....<=9数分别总共有几个
            count[i] = count[i] + count[i - 1];
        }
        for (i = R; i >= L; i--) {
            j = getDigit(arr[i], d);//获取该数的个位、十位、百位......上的数
            bucket[count[j] - 1] = arr[i];//将数放回到辅助空间
            count[j]--;
        }
        for (i = L, j = 0; i <= R; i++, j++) {
            arr[i] = bucket[j];
        }
    }
}
//获取该数的个位、十位、百位......上的数	
public static int getDigit(int x, int d) {		
    return ((x / ((int) Math.pow(10, d - 1))) % 10);
}