基数排序是一种非比较型整数排序算法，它通过按数位从低位到高位依次处理数字，将每个数字根据当前数位的数值分配到不同的“桶”中，再按桶的顺序收集回原数组，重复这一过程直到所有数位处理完毕。这种方法特别适合处理位数较少的整数，效率较高。
基数排序的基本思想¶
- 分配：按当前数位（如个位、十位、百位）将数字分配到对应的桶中。例如，个位数字为3的数放入桶3，十位数字为2的数放入桶2等。
- 收集：按桶的顺序（0到9）依次取出桶中的数字，放回原数组，完成一次数位的排序。
- 重复：对每一个数位（从低位到高位）重复上述分配和收集过程，直到所有数位处理完毕。
举例说明排序过程¶
以数组 [5, 3, 8, 12, 23, 100] 为例，逐步演示排序过程：
初始数组¶
[5, 3, 8, 12, 23, 100]
第一轮：处理个位（radix=1）¶
每个数的个位数字为：5（个位5）、3（个位3）、8（个位8）、12（个位2）、23（个位3）、100（个位0）。
- 分配到桶中：
桶0：[100]，桶2：[12]，桶3：[3, 23]，桶5：[5]，桶8：[8]，其他桶空。
- 收集回数组：[100, 12, 3, 23, 5, 8]。
第二轮：处理十位（radix=10）¶
每个数的十位数字为：100（十位0）、12（十位1）、3（十位0）、23（十位2）、5（十位0）、8（十位0）。
- 分配到桶中：
桶0：[100, 3, 5, 8]，桶1：[12]，桶2：[23]，其他桶空。
- 收集回数组：[100, 3, 5, 8, 12, 23]。
第三轮：处理百位（radix=100）¶
每个数的百位数字为：100（百位1）、3（百位0）、5（百位0）、8（百位0）、12（百位0）、23（百位0）。
- 分配到桶中：
桶0：[3, 5, 8, 12, 23]，桶1：[100]，其他桶空。
- 收集回数组：[3, 5, 8, 12, 23, 100]。
排序完成！
Java代码实现¶
import java.util.ArrayList;
import java.util.List;
public class RadixSort {
public static void radixSort(int[] arr) {
if (arr == null || arr.length == 0) {
return; // 空数组直接返回
}
// 1. 找到数组中的最大数，确定最大数位
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
// 2. 按数位从低位到高位处理（个位、十位、百位...）
for (int radix = 1; max / radix > 0; radix *= 10) {
// 创建10个桶（0-9），用ArrayList动态存储元素
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < 10; i++) {
buckets.add(new ArrayList<>());
}
// 3. 分配：将每个数按当前位数字放入对应桶
for (int num : arr) {
int currentDigit = (num / radix) % 10; // 获取当前位数字
buckets.get(currentDigit).add(num);
}
// 4. 收集：按桶顺序（0-9）放回原数组
int index = 0;
for (List<Integer> bucket : buckets) {
for (int num : bucket) {
arr[index++] = num;
}
}
}
}
// 测试代码
public static void main(String[] args) {
int[] arr = {5, 3, 8, 12, 23, 100};
System.out.println("排序前：" + java.util.Arrays.toString(arr));
radixSort(arr);
System.out.println("排序后：" + java.util.Arrays.toString(arr));
}
}
代码关键点解析¶
- 找到最大数：确定需要处理的最高数位（如最大数为100时，需处理百位）。
- 获取当前位：通过
(num / radix) % 10计算当前数位。例如：
- 个位：radix=1，(num / 1) % 10→ 直接取个位。
- 十位：radix=10，(num / 10) % 10→ 取十位。 - 桶的分配与收集：使用
ArrayList动态存储每个桶的元素，避免预先确定桶容量，收集时按顺序放回原数组。
时间与空间复杂度¶
- 时间复杂度：
O(d*(n+k))，其中d是最大数的位数，n是数组长度，k是基数（此处k=10）。若d和k固定，时间复杂度近似O(n)。 - 空间复杂度：
O(n+k)，需n个空间存储数组，k个桶。
总结¶
基数排序通过“按位分配-收集”的方式实现排序，适合整数排序，尤其当数字位数较少时效率较高。代码中使用 ArrayList 作为桶，简化了动态存储过程，且保持了排序的稳定性（相同数字相对顺序不变）。对于负数，可先分离正负再分别排序，最后合并。