Java数组实现基数排序电话号码方法

本文深入解析了如何用Java数组高效实现基数排序来处理电话号码排序这一典型场景，强调其不依赖元素比较、按位稳定分组的特性，以及针对11位手机号设计的完整技术路径：从正则清洗、字符提取、前导补零到标准化为int[]或char[][]数组；详细展开每轮计数排序的核心步骤——频次统计、前缀和转换、倒序分配与原地复制，并给出避免装箱、复用数组、预计算幂次、优化位提取等关键性能技巧，特别提醒大规模数据下的内存控制、缓存友好性及并行化边界，让读者一眼抓住“低开销、高可控、工业级可用”的实操精髓。

基数排序适合处理固定长度的整数或字符串（如电话号码），它不比较元素大小，而是按位分组计数，时间复杂度稳定为 O(d × (n + k))，其中 d 是位数（如 11 位手机号），k 是进制基数（通常取 10）。Java 中用数组实现时，核心是：用 计数数组统计每位数字频次 → 转为前缀和定位 → 倒序分配到临时数组 → 复制回原数组。关键在于避免对象创建、复用数组、严格按位处理。

电话号码预处理：统一格式与数值化

国内手机号通常为 11 位纯数字，但输入可能含空格、横线、+86 等。需先清洗并转为 long 或 int 数组（若全为 11 位且无前导零，可用 long 安全存储；若含国际区号或长度不一，建议转为 String 数组再按字符排序更稳妥）。实际中推荐统一截取/补零至 11 位后存入 int[] digits，每位存一个 0–9 的数字，便于后续按位索引。

• 用 StringBuilder 或正则 "[^0-9]" 提取所有数字，再截取末 11 位（或左补 0 至 11 位）
• 避免直接解析成 long：超大规模数据下 Long.valueOf() 会触发装箱，产生大量对象；改用字符数组遍历转换
• 示例："+86 138-1234-5678" → 提取 "8613812345678" → 取后 11 位 "3812345678" → 补前导零得 "03812345678"

单轮计数排序：稳定地按某一位排序

基数排序本质是多轮计数排序（Counting Sort），每轮处理 1 位（从个位开始，即最低有效位 LSD）。Java 中用原始 int 数组实现时，需两个辅助数组：count[10] 统计当前位各数字出现次数，output[n] 存放本轮结果。注意必须倒序遍历输入数组，才能保证相同数字的相对顺序不变（稳定性）。

• 初始化 count 全为 0；遍历所有数字，提取当前位（如第 i 位： (num / (int) Math.pow(10, i)) % 10，但更高效用移位或预计算幂）
• 对 count 做前缀和： count[j] += count[j-1]（j 从 1 到 9），此时 count[d] 表示 ≤ d 的数字总个数，即最大索引位置
• 倒序遍历原数组，对每个数 x 提取当前位 d，将 x 放入 output[count[d] - 1]，然后 count[d]--
• 最后用 System.arraycopy 将 output 复制回原数组

完整基数排序循环：从低位到高位迭代

对 11 位电话号码，需执行 11 轮计数排序（i = 0 到 10）。每轮只关注对应十进制位，无需关心数值大小。为提升性能，可预计算 10 的幂次方数组 int[] power = {1, 10, 100, ..., 10^10}，避免重复调用 Math.pow（该方法返回 double，有精度风险且慢）。

• 声明 int[] arr 存储所有电话号码的整数值（已标准化为 11 位无符号整数）
• 外层循环 for (int i = 0; i
• 提取位数公式优化为：int digit = (arr[j] / power[i]) % 10；确保 arr[j] ≥ 0，否则 % 运算行为异常
• 每轮复用同一组 output 和 count 数组，不重新 new，减少 GC 压力

内存与规模优化技巧

处理“超大规模”（如千万级）电话号码时，重点不是算法理论，而是数组局部性、缓存友好和内存控制。原始 int 数组比 Integer[] 节省一半内存且无 GC 开销；若数据远超内存，需分块排序 + 归并，但电话号码场景通常可全量驻留。

• 用 int[] 而非 long[]：11 位最大值 99999999999
• 避免 String 拼接或 substring：清洗阶段用 char[] 批量处理，用 Arrays.sort 不适用（非比较式），坚持自定义基数逻辑
• 并行化慎用：基数排序每轮依赖上一轮输出，无法简单 parallelStream；但可对超大 input 分段，各自 radix sort 后做 k-way merge

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~