算法系列（Algorithm）- 基数排序

1. 基数排序的基本原理

1.1 核心思想

基数排序的核心思想是"分配式排序"，它通过键值的各个位值，将要排序的元素分配到不同的"桶"中，然后按顺序收集这些元素，重复这个过程直到所有位都处理完毕。

1.2 两种实现方式

基数排序主要有两种实现方法：

1. 最低位优先法（LSD - Least Significant Digit first）：从最低位（个位）开始排序，然后依次处理十位、百位等，直到最高位。
2. 最高位优先法（MSD - Most Significant Digit first）：从最高位开始排序，然后递归地对每个子序列进行排序。

LSD方法更常用，因为它实现简单且稳定，而MSD方法在某些情况下效率更高，但实现更复杂。

2. 基数排序的工作步骤

基数排序的执行过程可以分为以下几个步骤：

1. 确定最大位数：找到待排序数组中的最大值，确定需要排序的轮数（即最大位数）
2. 创建桶：创建10个桶（0-9），用于存放每个位上的数字
3. 按位分配：从最低位开始，将每个元素按当前位的数字放入对应的桶中
4. 收集元素：按桶的顺序（0-9）将元素收集回原数组
5. 重复处理：对下一位重复步骤3-4，直到处理完所有位

2.1 具体示例

以数组[53, 3, 542, 748, 14, 214]为例：

第一轮（个位排序）：

• 个位为0：无
• 个位为1：无
• 个位为2：542
• 个位为3：53, 3
• 个位为4：14, 214
• 个位为5：无
• 个位为6：无
• 个位为7：无
• 个位为8：748
• 个位为9：无

收集后数组变为：[542, 53, 3, 14, 214, 748]

第二轮（十位排序）：

• 十位为0：3
• 十位为1：14, 214
• 十位为2：无
• 十位为3：无
• 十位为4：542, 748
• 十位为5：53
• 其余为无

收集后数组变为：[3, 14, 214, 542, 748, 53]

第三轮（百位排序）：

• 百位为0：3, 14, 53
• 百位为1：无
• 百位为2：214
• 百位为3：无
• 百位为4：无
• 百位为5：542
• 百位为6：无
• 百位为7：748
• 其余为无

最终排序结果为：[3, 14, 53, 214, 542, 748]

3. Java实现

以下是基数排序的完整Java实现代码：

import java.util.Arrays; public class RadixSort { /** * 基数排序主方法（LSD方式） * @param arr 待排序数组 */ public static void radixSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } // 1. 获取数组中的最大值，确定最大位数 int max = getMax(arr); // 2. 从个位开始，对每一位进行计数排序 for (int exp = 1; max / exp > 0; exp *= 10) { countingSortByDigit(arr, exp); } } /** * 获取数组中的最大值 * @param arr 数组 * @return 最大值 */ private static int getMax(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } /** * 按指定位数进行计数排序 * @param arr 待排序数组 * @param exp 当前位数（1表示个位，10表示十位，100表示百位...） */ private static void countingSortByDigit(int[] arr, int exp) { int n = arr.length; int[] output = new int[n]; // 输出数组 int[] count = new int[10]; // 计数数组，0-9共10个数字 // 初始化计数数组 Arrays.fill(count, 0); // 统计每个桶中的元素个数 for (int i = 0; i < n; i++) { int digit = (arr[i] / 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 = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } // 将排序结果复制回原数组 System.arraycopy(output, 0, arr, 0, n); } /** * 测试方法 */ public static void main(String[] args) { // 测试用例1 int[] arr1 = {53, 3, 542, 748, 14, 214}; System.out.println("原始数组1: " + Arrays.toString(arr1)); radixSort(arr1); System.out.println("排序后数组1: " + Arrays.toString(arr1)); // 测试用例2 int[] arr2 = {170, 45, 75, 90, 802, 24, 2, 66}; System.out.println("\n原始数组2: " + Arrays.toString(arr2)); radixSort(arr2); System.out.println("排序后数组2: " + Arrays.toString(arr2)); // 性能测试 testPerformance(); } /** * 性能测试：对10万个随机数进行排序 */ private static void testPerformance() { int size = 100000; int[] arr = new int[size]; // 生成随机数 for (int i = 0; i < size; i++) { arr[i] = (int)(Math.random() * 1000000); } long startTime = System.currentTimeMillis(); radixSort(arr); long endTime = System.currentTimeMillis(); System.out.println("\n排序" + size + "个随机数耗时: " + (endTime - startTime) + "毫秒"); // 验证排序正确性 boolean isSorted = true; for (int i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { isSorted = false; break; } } System.out.println("排序验证: " + (isSorted ? "正确" : "错误")); } }

4. 基数排序的变体实现

4.1 使用二维桶的实现方式

除了使用计数排序的变体外，还可以直接使用二维数组作为桶来实现基数排序：

public static void radixSortWithBucket(int[] arr) { if (arr == null || arr.length <= 1) { return; } // 获取最大值和最大位数 int max = arr[0]; for (int num : arr) { if (num > max) { max = num; } } int maxLength = String.valueOf(max).length(); // 创建10个桶（0-9） int[][] bucket = new int[arr.length]; int[] bucketCount = new int[10]; // 记录每个桶中元素的数量 // 从个位开始，逐位排序 for (int i = 0, exp = 1; i < maxLength; i++, exp *= 10) { // 将元素分配到桶中 for (int j = 0; j < arr.length; j++) { int digit = (arr[j] / exp) % 10; bucket[digit][bucketCount[digit]] = arr[j]; bucketCount[digit]++; } // 从桶中收集元素 int index = 0; for (int k = 0; k < 10; k++) { if (bucketCount[k] != 0) { for (int l = 0; l < bucketCount[k]; l++) { arr[index++] = bucket[k][l]; } bucketCount[k] = 0; // 清空计数，为下一轮做准备 } } } }

4.2 支持负数的基数排序

标准的基数排序只支持非负整数。如果需要支持负数，可以先分离正负数，分别排序后再合并：

public static void radixSortWithNegative(int[] arr) { if (arr == null || arr.length <= 1) { return; } // 分离正数和负数 List<Integer> positiveList = new ArrayList<>(); List<Integer> negativeList = new ArrayList<>(); for (int num : arr) { if (num >= 0) { positiveList.add(num); } else { negativeList.add(-num); // 转为正数处理 } } // 将List转换为数组 int[] positiveArr = positiveList.stream().mapToInt(i -> i).toArray(); int[] negativeArr = negativeList.stream().mapToInt(i -> i).toArray(); // 分别排序 if (positiveArr.length > 0) { radixSort(positiveArr); } if (negativeArr.length > 0) { radixSort(negativeArr); } // 合并结果：负数按降序，正数按升序 int index = 0; for (int i = negativeArr.length - 1; i >= 0; i--) { arr[index++] = -negativeArr[i]; // 转回负数 } for (int num : positiveArr) { arr[index++] = num; } }

5. 基数排序的性能分析

5.1 时间复杂度

基数排序的时间复杂度为 *O(d(n+k))**，其中：

• d：最大数字的位数
• n：待排序元素的数量
• k：基数（十进制中k=10）

具体分析：

• 每轮排序需要遍历所有元素一次，时间复杂度为O(n)
• 每轮需要处理k个桶，时间复杂度为O(k)
• 总共需要进行d轮排序
• 因此总时间复杂度为O(d*(n+k))

5.2 空间复杂度

基数排序需要额外的空间来存储：

• 输出数组：O(n)
• 计数数组/桶：O(k) 因此空间复杂度为O(n+k)。

5.3 稳定性

基数排序是一种稳定的排序算法。在分配元素到桶中时，如果两个元素在当前位上的数字相同，它们会按照原来的顺序放入桶中；在收集时也按照先进先出的原则，因此相等元素的相对顺序不会改变。

6. 基数排序的优缺点

6.1 优点

1. 时间复杂度较低：当d较小时，时间复杂度接近O(n)，比大多数比较排序算法（O(n log n)）更快
2. 稳定性好：保持相等元素的相对顺序，适用于需要稳定排序的场景
3. 适合整数排序：特别适合对整数进行排序，尤其是位数不多的情况
4. 可扩展性强：可以轻松扩展到其他进制（如二进制、十六进制）

6.2 缺点

1. 空间消耗大：需要额外的O(n+k)空间
2. 仅适用于整数：标准实现只适用于整数，对于浮点数或字符串需要特殊处理
3. 对负数需要特殊处理：需要先将负数转换为正数排序后再转换回来
4. 依赖位数：当最大数的位数很大时，性能会下降

7. 基数排序的应用场景

7.1 适用场景

1. 整数排序：特别是当整数范围不大且位数较少时
2. 多关键字排序：如按年、月、日排序日期
3. 字符串排序：可以按字符的ASCII码或Unicode码进行排序
4. 卡片排序机：最初就是为打孔卡片设计的排序方法

7.2 不适用场景

1. 浮点数排序：需要特殊处理
2. 数据范围极大：当最大数的位数非常多时
3. 内存受限环境：需要较多额外空间