【排序算法】之基数排序
一、算法介绍
基数排序是一种非比较型整数排序算法，其原理是将整数按低位到高位或者高位到低位的顺序，依次根据每一位的数值进行排序。通常情况下，基数排序会使用桶排序来处理每一位上的数值。
实现方法主要有如下：
-
最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
-
最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
-
整数数据：基数排序通常用于排序整数，因为它基于整数的位数来进行排序。对于正整数和负整数，只要数据被适当地处理（例如，先将所有数转换为非负数，排序后再转换回去），也可以使用基数排序。 -
固定长度的字符串：如果字符串长度固定，并且字符集大小有限，则可以将每个字符视为一个“位”，类似于整数中的位，从而应用基数排序。
时间数据：例如日期和时间，可以将其分解成不同的部分（如年、月、日、小时、分钟、秒），然后根据这些部分进行排序。 -
具有明确位权重的数据：基数排序适用于那些可以通过分解成几个部分，并且每个部分有明确权重的数据。例如，电话号码、邮政编码等。 -
数据范围不大：当数据的范围不是非常大时，基数排序能够高效工作。如果数据范围很大，那么可能需要大量的内存来存储计数数组或桶，这可能会降低算法的效率。
为了解释概念，这里通过一组正整数的数组： [53, 3, 542, 748, 14, 214, 154, 63, 616]
观察数组最大到百分位三位数字，对于那些不足百分位的，予以前缀补零处理，下面的示意图，即是按照个位、十位、百位的顺序依次排序
每次排序都是在前一次的结果上进行新一轮的排序换位。数字0~9即包含了每一位数上的所有可能值。问题的核心是确定最大位数，即从数组中的最大值确定，这是为了确定要进行多少轮排序，从个位，十分位，百分位…开始进行多轮排序。
二、代码实现
下面是一段代码，实现了上述数组的基数排序，采用了LSD方法，即最低位优先
核心方法是 countingSort()
package com.ds.project;
import java.util.Arrays;
import java.util.OptionalInt;
public class RadixSort {
// 获取最大值的位数
private static int getMaxDigits(int[] arr) {
OptionalInt optional = Arrays.stream(arr).max();
int max = 0;
if (optional.isPresent()) {
max = optional.getAsInt();
}
return (int) Math.log10(max) + 1;
}
// 计数排序
// 该方法用于对数组中每个元素的特定位进行排序，比如个位、十位、百位等
// 参数 arr: 待排序的数组 exp: 当前排序的位的权重（例如个位为1，十位为10，百位为100）
private static void countingSort(int[] arr, int exp, int cycle) {
int n = arr.length;
// 创建一个输出数组，用于保存排序后的结果
int[] output = new int[n];
// 创建一个计数数组，用于统计每个数字（0-9）出现的次数
int[] count = new int[10];
// 初始化计数数组，确保每个数字的初始计数为0
Arrays.fill(count, 0);
// 遍历原数组，统计每个数字在特定位上出现的次数
// 例如，对个位进行排序时，统计每个数字出现的次数
for (int j : arr) {
int index = (j / exp) % 10;
count[index]++;
}
System.out.println("第" + cycle + "轮当前位数的数字权重：" + Arrays.toString(count));
// 更新计数数组，使其每个索引处的值表示小于等于该索引的数字总数
// 例如,count[i]现在表示小于等于i的数字总数
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
System.out.println("第" + cycle + "轮统计小于每个个位数数字的计数：" + Arrays.toString(count));
// 根据计数数组构建输出数组
// 从后向前遍历原数组，根据每个数字在特定位上的值，将其放入输出数组的正确位置
for (int i = n - 1; i >= 0; i--) {
int index = (arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
// 将排序后的结果复制回原数组
// 使用System.arraycopy方法提高复制效率
System.arraycopy(output, 0, arr, 0, n);
}
// 基数排序主函数
public static void radixSort(int[] arr) {
int maxDigits = getMaxDigits(arr);
int cycle = 1;
// 从最低位开始，逐步向最高位排序
for (int exp = 1; maxDigits > 0; exp *= 10, maxDigits--) {
countingSort(arr, exp, cycle);
cycle++;
}
}
// 测试基数排序
public static void main(String[] args) {
System.out.println(3 / 100);
int[] arr = {53, 3, 542, 748, 14, 214, 154, 63, 616};
System.out.println("原始数组: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("排序后数组: " + Arrays.toString(arr));
}
}
笔者在代码上下文中加了一些循环排序过程中的打印信息，有些额外的无关代码。下面对核心方法 countingSort() 进行详细解释，只列举个位数统计排序的分析内容，其他十分位，百分位上的统计排序都是类似的不再分析。
步骤 1: 初始化计数数组
首先，我们需要一个计数数组 count，用于统计每个数字（0 到 9）出现的次数。
int[] count = new int[10]; // 0 到 9 的计数数组
Arrays.fill(count, 0); // 初始化为 0
步骤 2: 统计每个数字出现的次数
遍历原数组 arr，统计每个数字在当前位上的出现次数。
for (int j : arr) {
int index = (j / exp) % 10; // 当前位上的数字
count[index]++; // 计数
}
假设 exp = 1（即处理个位数），那么：
- 53 的个位是 3，count[3]++，count 变为 [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
- 3 的个位是 3，count[3]++，count 变为 [0, 0, 0, 2, 0, 0, 0, 0, 0, 0]
- 542 的个位是 2，count[2]++，count 变为 [0, 0, 1, 2, 0, 0, 0, 0, 0, 0]
- 748 的个位是 8，count[8]++，count 变为 [0, 0, 1, 2, 0, 0, 0, 0, 1, 0]
- 14 的个位是 4，count[4]++，count 变为 [0, 0, 1, 2, 1, 0, 0, 0, 1, 0]
- 214 的个位是 4，count[4]++，count 变为 [0, 0, 1, 2, 2, 0, 0, 0, 1, 0]
- 154 的个位是 4，count[4]++，count 变为 [0, 0, 1, 2, 3, 0, 0, 0, 1, 0]
- 63 的个位是 3，count[3]++，count 变为 [0, 0, 1, 3, 3, 0, 0, 0, 1, 0]
- 616 的个位是 6，count[6]++，count 变为 [0, 0, 1, 3, 3, 0, 1, 0, 1, 0]
此时 count 数组为 [0, 0, 1, 3, 3, 0, 1, 0, 1, 0]。
步骤 3: 更新计数数组
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
第二次遍历 count 数组，将每个位置的计数值调整为小于或等于该位置的所有数字的累计数量，这一步骤是为了确定每个数字在 output 数组中的最终位置
为什么是要统计小于等于呢？因为个位数数字可能会有重复的，所以要包含自身
count数组变成 [0, 0, 1, 4, 7, 7, 8, 8, 9, 9]，索引对应的0~9，索引为2即表示个位数小于或等于2的只有一个，那么个位数是2的就是output数组的第一个元素。索引为3的表示个位数小于或等于3的有四个，去掉为2则说明个位数是3的有三个，这不好确定位置，只能保持个位数为3的元素在原始数组中的相对位置顺序，具体怎么实现请看如下步骤
步骤 4: 构建输出数组
下面循环代码是核心部分，实现了排序的稳定性和正确性
for (int i = n - 1; i >= 0; i--) {
int index = (arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
代码是从后往前遍历原始数组的，为什么需要从后往前呢？就是为了保证当个位数的数字相同时，顺序不变化。
初始数组顺序如下：
[53, 3, 542, 748, 14, 214, 154, 63, 616]
count计数数组为 [0, 0, 1, 4, 7, 7, 8, 8, 9, 9]，
最后一位元素616的个位数字6，那么个位数字小于或者等于6的元素个数是多少呢count[6] = 8。即当前元素在整个新构建的数组output中应该排在第8的位置，索引是从下标0开始的，所以第8个元素的索引位置为7，output[7] = 616。
那为什么接着需要 count[index]-- 呢？其实是为了保证后续的个位数数字仍然为6时，能被放置在正确的位置上，即个位数都是6的元素之间位置顺序相对不移动。
上述初始数组列子改成如下：
[53, 3, 542, 748, 14, 214, 156, 63, 616]
count计数统计数组变成：[0, 0, 1, 4, 6, 6, 8, 8, 9, 9]
最后一位元素还是616，count[6] = 8，正确放置后到output数组的第8个位置，即output[7] = 616，另count[6] = count[6]-1 = 7，即往前遍历时，再遇到个位数是6的元素，比如156，那这个156元素就应该放置到第output输出数组的第7个位置，output[6] = 156。
在放置156元素之前，倒数第二个元素63放置到哪里呢？count[3] = 4，output[3] = 63，即63应放置到output输出数组的第四个位置。
从后往前遍历的作用是，可以将不同的个位数数字在初次遇到时，确定其在output输出数组中的位置，通过减少计数个数来确保再遇到相同个位数值时，它的位置能在上一次相同个位数的位置往前移动一位，从后往前遍历保证了相同个位数的相对位置保持不变。
三、拓展研究
以上数组都是正整数，那数组中包含负整数咋办呢？很简单先找出最小值，把每个元素都加上最小值的绝对值，然后进行排序，再把排序后的结果再减去原最小值的绝对值，即可得到正确的排序，以下是代码示例
public static void main(String[] args) {
System.out.println(3 / 100);
int[] arr = {53, 3, -542, 748, -14, 214, 156, 63, 616};
System.out.println("原始数组: " + Arrays.toString(arr));
int min = getMin(arr);
System.out.println("最小值：" + min);
// 将数组中的元素加上最小值的绝对值，都变成正数
int[] newArr = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
newArr[i] = arr[i] + Math.abs(min);
}
//排序
radixSort(newArr);
//减去原最小值的绝对值
for (int i = 0; i < arr.length; i++) {
newArr[i] = newArr[i] - Math.abs(min);
}
System.out.println("排序后数组: " + Arrays.toString(newArr));
}
