今天手敲 基数排序 代码的时候发现结果不对，这里简记一下原因。

第一版代码（错误）

public void radixSort(int[] arr) {
    // 1. 获取 arr 的最大位数
    int maxDigit = Arrays.stream(arr).max().getAsInt();
    int maxLen = String.valueOf(maxDigit).length();
    // 2. 定义 桶 和 计数数组
    int[][] buckets = new int[10][arr.length];
    int[] bucketCounts = new int[10];
    // 3. 进行 k 次排序
    for (int i = 0, n = 1; i < maxLen; i++, n *= 10) {
        // 3.1 将 arr 中的元素放入对应的桶中
        for (int j = 0; j < arr.length; j++) {
            int digitOfCurrent = arr[j] / n % 10;
            buckets[digitOfCurrent][bucketCounts[digitOfCurrent]] = arr[j];
            bucketCounts[digitOfCurrent]++;
        }
        // 3.2 对每个桶中的元素取出并覆盖 arr
        int index = 0;
        for (int k = 0; k < bucketCounts.length; k++) {
        // 注意，这里从 bucketCounts 中取值的时候是从后往前取得
            while (bucketCounts[k] > 0){
                arr[index++] = buckets[k][bucketCounts[k] - 1];
                bucketCounts[k]--;
            }
        }
    }
}

结果

这里以数组 arr = { 1, 52, 478, 12, 83, 7, 45, 333 }为例，

debug

第一版代码在进行从 bucketCounts数组中取值时是从后往前取值的，虽然这样在第一次循环是不会出现问题，但是在后续的循环中会导致取值错乱现象。
第一次外层循环结束后（即 i = 0 结束后）
可以看到第一次结束后并没有对 buckets 进行清空。

第二次外层循环结束后（即 i = 1结束后）

第三次外层循环结束后（即 i = 2结束后）

第二版代码（正确）

public void radixSort(int[] arr) {
    // 1. 获取 arr 的最大位数
    int maxDigit = Arrays.stream(arr).max().getAsInt();
    int maxLen = String.valueOf(maxDigit).length();
    // 2. 定义 桶 和 计数数组
    int[][] buckets = new int[10][arr.length];
    int[] bucketCounts = new int[10];
    // 3. 进行 k 次排序
    for (int i = 0, n = 1; i < maxLen; i++, n *= 10) {
        // 3.1 将 arr 中的元素放入对应的桶中
        for (int j = 0; j < arr.length; j++) {
            int digitOfCurrent = arr[j] / n % 10;
            buckets[digitOfCurrent][bucketCounts[digitOfCurrent]] = arr[j];
            bucketCounts[digitOfCurrent]++;
        }
        // 3.2 对每个桶中的元素取出并覆盖 arr
        int index = 0;
        for (int k = 0; k < bucketCounts.length; k++) {
            if (bucketCounts[k] != 0) {
                // 注意这里一定要从前面开始取值
                for (int l = 0; l < bucketCounts[k]; l++) {
                    arr[index++] = buckets[k][l];
                }
                bucketCounts[k] = 0;
            }
        }
    }
}