基数排序 | 青柠

题目

存在如下数组通过基数排序算法进行排序：

【12、451、35、21、4571、111、20、130、66、68、17、36】

实现代码

基数排序的原理就是先对个位进行排序，按序放入原数组，再对十位进行排序，再按序放入数组……

最终得到一个排好序的数组
（LSD算法）

以下是基数排序算法中的LSD算法实现：

// 基数排序
void radixSortLSD(int[] nums) {
    int min = Integer.MAX_VALUE;
    for (int num : nums) {
        min = Math.min(min, num);
    }

    // 根据最小元素，将所有元素转化为从零开始的非负数
    int offset = -min;
    for (int i = 0; i < nums.length; i++) {
        nums[i] += offset;
    }

    int max = Integer.MIN_VALUE;
    for (int num : nums) {
        max = Math.max(max, num);
    }

    // 计算最大元素的位数
    int maxLen = 0;
    while (max > 0) {
        max /= 10;
        maxLen++;
    }

    // 从低位到高位，依次对每一位进行计数排序
    for (int k = 0; k < maxLen; k++) {
        countSort(nums, k);
    }

    // 将所有元素转化回原来的值
    for (int i = 0; i < nums.length; i++) {
        nums[i] -= offset;
    }
}


// 基数排序使用的计数排序算法函数
// 已经确保 nums 中的元素都是非负数
// k 是当前需要排序的位数
void countSort(int[] nums, int k) {
    // 基数排序中每一位十进制数的取值范围是 0~9
    int[] count = new int[10];

    // 对每个元素的第 k 位进行计数
    for (int num : nums) {
        int digit = (num / (int) Math.pow(10, k)) % 10;
        count[digit]++;
    }

    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 按照第 k 位的值对元素进行排序
    int[] sorted = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        int digit = (nums[i] / (int) Math.pow(10, k)) % 10;
        sorted[count[digit] - 1] = nums[i];
        count[digit]--;
    }

    // 把排序结果复制回原数组
    for (int i = 0; i < nums.length; i++) {
        nums[i] = sorted[i];
    }
}

下面对部分代码进行讲解：

代码解释

代码片段一

1
2
3

for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
}

计算“小于等于当前角标数值的数量”

比如：以个位数为例，并且 nums 总数为12个

计算之前：

个位数为 0 的数 : 2个

个位数为 1 的数 : 4个

个位数为 2 的数 : 1个

个位数为 3 的数 : 0个

个位数为 4 的数 : 0个

……

i	0	1	2	3	4	5	6	7	8	9
count(i)	2	4	1	0	0	1	2	1	1	0

计算之后：

i	0	1	2	3	4	5	6	7	8	9
count(i)	2	6	7	7	7	8	10	11	12	12

表示：

角标0：个位数上存在2个小于等于0的数据；

角标1：个位数上存在6个小于等于1的数据；

角标2：个位数上存在7个小于等于2的数据；

角标3：个位数上存在6个小于等于3的数据；

……

代码片段二

// 按照第 k 位的值对元素进行排序
int[] sorted = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
  	// k位上的值：个位、十位、百位……
    int digit = (nums[i] / (int) Math.pow(10, k)) % 10;
    sorted[count[digit] - 1] = nums[i];
    count[digit]--;
}