基数排序

基数排序已经不再是一种常规排序方法，它更多地像一种排序方法的应用，基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。
多关键字排序的思路是将待排数据里的排序关键字拆分成多个排序关键字：第1 子关键字、第2子关键字、第3子关键字……然后，根据子关键字对待排数据进行排序。
多关键字排序时有两种解决方案：

• 最高位优先法MSD（Most Significant Digit first）
• 最低位优先法LSD（Least Significant Digit first）

例如，对如下数据序列进行排序。
192，221，13，23
可以观察到它每个数据至多只有3位，因此可以将每个数据拆分成3个关键字：百位（高位）、十位、个位（低位）。
如果按照习惯思维，会先比较百位，百位大的数据大；百位相同的再比较十位，十位大的数据大；最后再比较个位。人的习惯思维是最高位优先方式。
如果按照人的思维方式，计算机实现起来有一定困难，当开始比较十位时，程序还需要判断它们的百位是否相同—这就人为地增加了难度。计算机通常会选择最低位优先法，如下所示。
第1轮先比较个位，对个位关键字排序后得到序列为：
221，192，13，23
第2轮再比较十位，对十位关键字排序后得到序列为：
13，23，221，192
第3轮再比较百位，对百位关键字排序后得到序列为：
13，23，192，221
从上面介绍可以看出：基数排序方法对任一子关键字排序时必须借助于另一种排序方法，而且这种排序方法必须是稳定的。
如果这种排序算法不稳定，比如上面排序过程中，经过第2 轮十位排序后，13 位于23之前，在第3轮百位排序时，如果该排序算法是稳定的，那么13依然位于23之前；如果该算法不稳定，那可能13跑到23之后，这将导致排序失败。
现在的问题是：对子关键字排序时，到底选择哪种排序方式更合适呢？答案是桶式排序。回顾桶式排序的两个要求：

• 待排序列的所有值处于一个可枚举范围内；
• 待排序列所在的这个可枚举范围不应该太大。

对于多关键字拆分出来的子关键字，它们一定位于0～9这个可枚举范围内，这个范围也不大，因此用桶式排序效率非常好。

public class MultiKeyRadixSort {

    /**
     *
     * @param data 待排序数组
     * @param radix 指定关键字拆分进制。如 radix=10，表明按10进制拆分
     * @param d 指定将关键字拆分成几个子关键字
     */
    public static void radixSort(int[] data, int radix, int d){
        System.out.println("开始排序：");
        int arrayLength = data.length;
        //需要一个临时数组
        int[] tmp = new int[arrayLength];

        //buckets数组是桶式排序
        //例如：10进制的话，就是0-9 只有10个数，所有长度就10即可
        int[] buckets = new int[radix];

        //依次从最高位的子关键字对待数据进行排序
        //下面循环中rate用于保存当前计算的位（比如十位时 rate=10)
        for (int i = 0, rate = 1; i < d; i++) {
            //重置count数组，开始统计第二个关键字
            Arrays.fill(buckets, 0);

            //将data数组的元素复制到temporary数组中进行缓存
            System.arraycopy(data, 0, tmp, 0, arrayLength);

            //计算每个待排序数据的子关键字
            for (int j = 0; j < arrayLength; j++) {
                //计算数据指定位上的子关键字
                int subKey = (tmp[j] / rate) % radix;
                buckets[subKey]++;
            }
            for (int j = 1; j < radix; j++) {
                buckets[j] = buckets[j] + buckets[j - 1];
            }

            //按子关键字对指定数据进行排序
            for (int m = arrayLength - 1; m >= 0; m--) {
                int subKey = (tmp[m] / rate) % radix;
                data[--buckets[subKey]] = tmp[m];
            }
            System.out.println("对" + rate + "位上子关键字排序：" + Arrays.toString(data));

            rate *= radix;
        }
    }

    public static void main(String[] args) {
        int[] data = {1100, 192, 221, 12, 13};

        System.out.println("排序前：\n" + Arrays.toString(data));
        radixSort(data, 10, 4);
        System.out.println("排序后：\n" + Arrays.toString(data));
    }
}