[数据结构与算法]基数排序的基本思想与模板分析【排序算法篇】

基本思想

假如来了一个混乱数组org，我们需要将它排好序。我们做如下操作。

1. 先得到该数组中最大的那个数MAX。
2. 创建一个数组ans，该数组的长度就是MAX。
3. 接下来遍历混乱数组org，ans[org[i]]=org[i];。

以上的操作很简单，我们可以轻易的看出其缺点就是太浪费空间。
那么基数排序，则是对以上操作进行了优化。基数排序我们做如下操作。

1. 创建桶数组，其长度为20（考虑正负数）。
2. 接下来循环，第一轮是取每个数字的个位数，在桶数组对应位置+1。
3. 根据桶的个数生成位置。
4. 获取位置，更新原数组。
5. 第二轮循环开始，这次是取每个数字的百位数，重复以上操作。
6. 接下来依次类推，循环次数为原数组最大值的位数。

图示

以下动图取自网络

代码模板

public void get() {
    int[] arr = new int[]{17, -13, 20, -7, 2, 17, 12};

    radixSort(arr);

    for (int i : arr) {
        System.out.println(i);
    }
}


/**
 * 基数排序（升序）
 * @param arr 原数组
 */
public void radixSort(int[] arr) {

    //辅助数组
    int[] tmp = new int[arr.length];
    //基数
    int n = 1;
    //初始化桶数组。位置【0~9】存放0~9，位置【11~19】存放-1~-9
    int[] bin = new int[20];
    while (true) {

        /**
         * 该for循环将根据基数，确定原数组每个数字对应位置，在该位置上添加一个桶（表示存放该数字）
         * 如在第一轮while循环中基数n是1，则取个位上的数字进行桶计算，原数组有17这个数字，则在7号桶上+1。
         * 在本次案例{17, -13, 20, -7, 2, 17, 12}中，
         *      第一轮while循环中，该for循环结束时：bin={1,0,2,0,0,0,0,2,0,0,0,0,0,1,0,0,0,1,0,0}
         */
        for (int val : arr) {
            int j = (val / n) % 10;//得到该数字在桶数组中的位置
            //以下对正负数的位置区间进行确定，位置【0~9】存放0~9，位置【11~19】存放-1~-9
            if (j >= 0) {
                bin[j]++;//在对应位置上+1，表示该数字在该位置占一位的空间
            } else {
                bin[10 - j]++;
            }
        }

        //当所有的数字全都在‘0’号桶中，意味着原数组中的数字没有比基数还大的，基数排序到此结束，退出循环。
        if (bin[0] == arr.length) break;

        /**
         * 接下来我们根据桶的个数，生成位置
         * 我们将考虑正数与负数（在这个案例中，我们将0看作正数）
         * 
         * 我们先对负数的桶位置进行计算，位置【11~19】存放-1~-9，
         *      因为是升序，所以越小的数占据越前的位置。bin[i]修改为：当前数值+bin[i+1]。
         * 接下来对正数的桶位置进行计算，bin[i]修改为：当前数值+bin[i-1]。
         * 
         * 以下两个循环结束后，bin={3,3,5,5,5,5,5,7,7,7,0,0,0,1,1,1,1,2,2,2}
         */
        for (int i = 18; i > 10; i--) {
            bin[i] += bin[i + 1];
        }
        bin[0]+=bin[11];
        for (int i = 1; i < 10; i++) {
            bin[i] += bin[i - 1];
        }

        //获取位置，在辅助数组中在bin[j]位置上存入数字
        for (int i = tmp.length - 1; i >= 0; i--) {
            int j = (arr[i] / n) % 10;
            if (j >= 0) {
                bin[j]--;
                tmp[bin[j]] = arr[i];
            } else {
                bin[10 - j]--;
                tmp[bin[10 - j]] = arr[i];
            }
        }

        //更新原数组
        System.arraycopy(tmp, 0, arr, 0, tmp.length);

        //基数每轮提升一个数量级，如1->10->100...
        n *= 10;

        //清空桶，以便下次存放
        Arrays.fill(bin, 0);
    }
}

• $时间复杂度为O(d(n+r))，空间复杂度为O(n)$