基数排序适合对非负整数高效稳定排序，按位逐轮分配收集，用计数排序作子过程实现lsd方式；含负数时通过统一偏移转为非负再还原。
基数排序适合对非负整数进行高效稳定排序，它不比较元素大小，而是按数字的“位”（个、十、百……）逐轮分配和收集。Java 中可借助计数排序作为子过程，实现 LSD（最低位优先）方式的基数排序。
理解基数排序的核心思路
基数排序把每个整数看作 d 位 b 进制数（常用十进制，b=10），从最低位开始，对每一位执行一次稳定排序（通常用计数排序），共进行 d 轮。关键在于：每轮排序必须稳定，才能保证高位排序不破坏低位已排好的相对顺序。
处理负数和通用整数的技巧
标准基数排序要求输入为非负数。若数组含负数，可统一偏移：找出最小值 minVal，将所有数加上 -minVal 变成非负，排序后再减去该偏移还原。例如 [-5, 3, -1] → 加 5 得 [0, 8, 4] → 排序后 [0, 4, 8] → 减 5 得 [-5, -1, 3]。
Java开发手册规约集合，基于阿里巴巴Java开发手册（嵩山版）。 涵盖7大维度：编程规约、异常日志、单元测试、安全规约、MySQL数据库、工程结构、设计规约。 当用户需要：(1) 编写或审查Java代码 (2) 检查命名/代码规范 (3) 处理异常和日志 (4) 编写单元测试 (5) 安全编码 (6) 数据库设...
Java 实现步骤（LSD + 计数排序）
以十进制为例，按个、十、百……位处理：
- 计算最大数的位数（如 123 → 3 位），决定循环轮数
- 每轮提取当前位数字：(num / digit) % 10，其中 digit = 1, 10, 100…
- 用长度为 10 的计数数组统计每位数字（0–9）出现次数
- 做前缀和，得到每个数字在输出数组中的位置范围
- 倒序遍历原数组（保证稳定性），根据当前位数字将元素放入临时数组对应位置
- 将临时数组复制回原数组，进入下一轮
代码示例（支持负数）
// 注意：仅作逻辑演示，生产环境建议封装为方法
public static void radixSort(int[] arr) {
if (arr.length == 0) return;
// 处理负数：找最小值并偏移
int minVal = Arrays.stream(arr).min().orElse(0);
int offset = minVal
int[] shifted = Arrays.stream(arr).map(x -> x + offset).toArray();
// 找最大值确定位数
int max = Arrays.stream(shifted).max().orElse(0);
for (int digit = 1; max / digit > 0; digit *= 10) {
countingSortByDigit(shifted, digit);
}
// 还原并写回原数组
for (int i = 0; i
arr[i] = shifted[i] - offset;
}
}
private static void countingSortByDigit(int[] arr, int digit) {
int[] output = new int[arr.length];
int[] count = new int[10]; // 十进制，0–9
// 统计每位数字频次
for (int num : arr) {
int d = (num / digit) % 10;
count[d]++;
}
// 前缀和，得到各数字结尾索引
for (int i = 1; i
count[i] += count[i - 1];
}
// 倒序填入 output（保持稳定）
for (int i = arr.length - 1; i >= 0; i--) {
int d = (arr[i] / digit) % 10;
output[--count[d]] = arr[i];
}
// 复制回 arr
System.arraycopy(output, 0, arr, 0, arr.length);
}
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
