基数排序 Java 实现 + 思路详解

一、核心思路基数排序属于分配式排序不基于元素比较 思想按位数依次排序从低位到高位最低位优先 LSD流程获取数组中最大值确定最大有多少位准备 0~9 共 10 个桶代表数字当前位 0-9依次对 ** 个位、十位、百位……** 进行一轮桶排序根据当前位数字把元素放入对应桶按桶顺序依次取出元素覆盖原数组所有位数处理完成数组整体有序。⚠️特性面试重点时间复杂度\(O(k\times n)\)n 元素个数k 最大数字位数数据量大、位数少时效率极高稳定排序需要额外空间只适合非负整数负数需要额外处理不属于比较排序二、完整 Java 代码LSD 最低位优先java运行import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int[] arr {53, 3, 542, 748, 14, 214, 154, 61, 666}; System.out.println(排序前 Arrays.toString(arr)); radixSort(arr); System.out.println(排序后 Arrays.toString(arr)); } public static void radixSort(int[] arr) { if (arr null || arr.length 1) { return; } // 1. 获取数组最大值确定最大位数 int max arr[0]; for (int num : arr) { if (num max) { max num; } } // 二维数组10个桶每个桶存放元素 // bucket[0] 存当前位为0的数字 ... bucket[9]存9 int[][] bucket new int[10][arr.length]; // bucketElementCounts[i]记录第i个桶当前存放多少个元素 int[] bucketElementCounts new int[10]; // 循环处理每一位个位、十位、百位... for (int digit 1; max / digit 0; digit * 10) { // 【第一步放入桶中】 for (int num : arr) { // 取出当前位的值 int remainder num / digit % 10; bucket[remainder][bucketElementCounts[remainder]] num; bucketElementCounts[remainder]; } // 【第二步从桶中依次取出放回原数组】 int index 0; for (int i 0; i 10; i) { // 当前桶不为空 if (bucketElementCounts[i] 0) { for (int k 0; k bucketElementCounts[i]; k) { arr[index] bucket[i][k]; } } // 清空桶计数下一轮复用 bucketElementCounts[i] 0; } } } }三、简单推演示例数组[53, 3, 542, 748, 14]第一轮个位排序个位3,3,2,8,4 入桶顺序取出 →[542,53,3,14,748]第二轮十位排序十位4,5,0,1,4 取出 →[3,14,542,748,53]第三轮百位排序百位0,0,5,7,0 取出 →[3,14,53,542,748]完成排序四、注意事项上面代码仅支持非负整数 如果要支持负数可以把数字分成正数、负数两组负数取绝对值排序反转后加上负号再合并。桶的实现方式除二维数组外也可以用ListInteger[] buckets写法更简洁基数排序适合手机号、身份证、数字编号等固定长度数字场景。拓展List 简化版本可读性更强推荐面试手写备选java运行import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class RadixSortList { public static void main(String[] args) { int[] arr {53, 3, 542, 748, 14, 214, 154, 61, 666}; radixSort(arr); System.out.println(Arrays.toString(arr)); } public static void radixSort(int[] arr) { int max arr[0]; for (int num : arr) max Math.max(max, num); ListInteger[] buckets new List[10]; for (int i 0; i 10; i) { buckets[i] new ArrayList(); } for (int digit 1; max / digit 0; digit * 10) { // 入桶 for (int num : arr) { int r num / digit % 10; buckets[r].add(num); } // 回写数组 int idx 0; for (ListInteger bucket : buckets) { for (Integer val : bucket) { arr[idx] val; } bucket.clear(); } } } }