基数排序支持负数的数组实现采用偏移法：先求最小值minVal，设offset=-minVal，将所有数加offset转为非负数；再用LSD十进制基数排序（每轮计数排序稳定分桶）；最后统一减offset还原。
基数排序在 java 中用数组实现时，负数不能直接按常规的“按位分桶”处理，因为负数的补码表示会导致高位为 1，直接按二进制位或十进制位分桶会打乱顺序。解决思路是：将负数和非负数分离，对负数取绝对值排序后逆序（即从大到小排），再整体反转并拼接到非负数排序结果前；或者更统一的做法——使用偏移量（offset）将所有数映射到非负区间，排序后再还原。下面给出一种简洁、稳定、基于十进制位、支持负数的数组实现。
核心思想：偏移法 + 计数排序作为子过程
不修改原始数值含义的前提下，先找出数组最小值 minVal，定义偏移量 offset = -minVal（若 minVal ≥ 0，则 offset = 0）。将每个数加上 offset，全部转为 ≥ 0 的整数；对这些非负数做标准的 LSD（最低位优先）基数排序；最后减去 offset 还原结果。该方法保持稳定性，且无需分支处理正负逻辑。
关键步骤说明
- 确定位数范围：计算最大值（加 offset 后）的十进制位数，即循环轮数。例如数组为 [-123, 45, -6, 0]，minVal = -123 → offset = 123，转换后为 [0, 168, 117, 123]，最大值 168 → 3 轮（个、十、百）
- 每轮使用计数排序（稳定）：对当前位（如个位：x % 10）分桶。桶大小固定为 10（0–9），用长度为 10 的计数数组统计频次，再通过前缀和计算各桶输出起始位置，倒序遍历原数组完成本轮重排（保证稳定性）
- 注意还原时机：仅在最终返回前统一减 offset；中间所有排序操作都在偏移后的非负数上进行
完整可运行代码示例
以下为基于 int 数组的完整实现（无额外集合类，纯数组操作）：
Java注释规范Skills
下载
当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。
public static void radixSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
<pre class='brush:java;toolbar:false;'>// 步骤1：找 min 和 max，确定 offset
int minVal = arr[0], maxVal = arr[0];
for (int x : arr) {
if (x < minVal) minVal = x;
if (x > maxVal) maxVal = x;
}
int offset = -minVal;
int n = arr.length;
// 创建临时数组存放偏移后数据（避免修改原数组中途出错）
int[] temp = new int[n];
for (int i = 0; i < n; i++) {
temp[i] = arr[i] + offset;
}
// 步骤2：计算最大值（偏移后）的位数
int maxAfterOffset = maxVal + offset;
int digits = (maxAfterOffset == 0) ? 1 : (int) Math.log10(maxAfterOffset) + 1;
// 步骤3：LSD 基数排序（从个位开始）
int[] output = new int[n]; // 每轮输出数组
int[] count = new int[10]; // 0–9 十个桶
for (int d = 0; d < digits; d++) {
// 清空计数数组
Arrays.fill(count, 0);
// 统计当前位（10^d）上的数字频次
int exp = (int) Math.pow(10, d);
for (int x : temp) {
int digit = (x / exp) % 10;
count[digit]++;
}
// 前缀和：count[i] 表示 ≤ i 的数字个数，用于确定输出位置
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 倒序遍历，保证稳定性
for (int i = n - 1; i >= 0; i--) {
int digit = (temp[i] / exp) % 10;
output[--count[digit]] = temp[i];
}
// 将 output 复制回 temp，进入下一轮
System.arraycopy(output, 0, temp, 0, n);
}
// 步骤4：还原原始值并写回 arr
for (int i = 0; i < n; i++) {
arr[i] = temp[i] - offset;
}}
立即学习“Java免费学习笔记（深入）”；
使用注意事项与优化提示
- 时间复杂度仍是 O(d·(n+k))，其中 d 是最大位数，k=10（桶数），对整数数组很高效；空间复杂度 O(n)
- 不适用于 long 或超大范围整数：因 Math.pow 和 log10 在大数下可能精度丢失；可改用字符串长度或循环除 10 计位数更稳妥
- 若只含负数或零，offset 可能很大但无影响：只要 int 不溢出（temp[i] = arr[i] + offset ≤ Integer.MAX_VALUE），就安全；极端情况可加溢出检查
- 如需更高性能，可预分配 output 和 count 数组一次复用，避免多轮 new
这种偏移法逻辑清晰、代码易懂、兼容性强，是处理负数基数排序最推荐的数组级实现方式。不复杂但容易忽略偏移还原这一步，务必确保最后统一减 offset。
