一、为什么我们需要基数排序
排序算法是计算机科学中最基础也最常用的算法之一。我们熟悉的快速排序、归并排序、堆排序等都是基于比较的排序算法，它们的时间复杂度通常是O(n log n)。但在某些特定场景下，比如处理大量整数数据时，这些算法可能并不是最优解。这时候，基数排序（Radix Sort）就派上用场了。
基数排序是一种非比较型整数排序算法，它的核心思想是“按位分配，逐位排序”。听起来有点抽象？别急，我们慢慢来。
举个例子，假设我们有一组三位数的整数：
[170, 45, 75, 90, 802, 24, 2, 66]
如果我们用传统的比较排序，比如快速排序，它需要多次比较和交换元素。而基数排序则不同，它不直接比较数字的大小，而是按照每一位的数字（个位、十位、百位等）进行分配和收集，最终完成排序。
二、基数排序的基本原理
基数排序有两种常见的实现方式：
- 最低位优先（LSD, Least Significant Digit first）：从最低位（个位）开始排序，逐步向高位（十位、百位等）推进。
- 最高位优先（MSD, Most Significant Digit first）：从最高位开始排序，逐步向低位推进。
我们以LSD为例，详细讲解基数排序的步骤。
示例：LSD基数排序
假设我们有以下数组：
[170, 45, 75, 90, 802, 24, 2, 66]
第一步：按个位数字分配
我们创建10个桶（0-9），然后根据个位数字将数字放入对应的桶中：
- 0: [170, 90]
- 2: [802, 2]
- 4: [24]
- 5: [45, 75]
- 6: [66]
然后按顺序收集：
[170, 90, 802, 2, 24, 45, 75, 66]
第二步：按十位数字分配
再次分配：
- 0: [802, 2]
- 2: [24]
- 4: [45]
- 6: [66]
- 7: [170, 75]
- 9: [90]
收集：
[802, 2, 24, 45, 66, 170, 75, 90]
第三步：按百位数字分配
最后分配：
- 0: [2, 24, 45, 66, 75, 90]
- 1: [170]
- 8: [802]
收集：
[2, 24, 45, 66, 75, 90, 170, 802]
最终，数组已经排好序了！
三、基数排序的代码实现（Java示例）
下面我们用Java来实现基数排序：
import java.util.Arrays;
public class RadixSort {
public static void radixSort(int[] arr) {
// 找到数组中的最大值，确定需要排序的轮数
int max = Arrays.stream(arr).max().getAsInt();
// 从个位开始，逐位排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
private static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n]; // 存储排序后的数组
int[] count = new int[10]; // 计数数组（0-9）
// 统计当前位（exp）的数字出现次数
for (int num : arr) {
int digit = (num / exp) % 10;
count[digit]++;
}
// 计算累加次数，用于确定数字在output中的位置
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) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("排序前: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
}
}
代码解析：
radixSort方法负责确定排序的轮数（由最大值的位数决定）。countingSort方法实现基于当前位的计数排序。- 每次排序后，数据会被重新收集到
output数组中，并复制回原数组。
四、基数排序的优缺点
优点：
- 时间复杂度低：基数排序的时间复杂度是O(nk)，其中n是元素个数，k是数字的位数。如果k较小（比如32位整数），它的性能可能优于O(n log n)的比较排序。
- 稳定性：基数排序是稳定的排序算法，相同值的元素在排序后相对顺序不变。
缺点：
- 仅适用于整数：基数排序依赖于数字的位数分配，因此不适用于浮点数或字符串（除非进行特殊处理）。
- 空间消耗较大：需要额外的存储空间（桶或计数数组）。
五、基数排序的应用场景
- 大数据量的整数排序：比如数据库索引、大规模数据分析。
- 多关键字排序：比如先按年龄排序，再按薪资排序。
- 基数排序的变种：如字符串的字典序排序（可以看作多关键字排序）。
六、注意事项
- 数据范围影响性能：如果数字位数差异很大（比如1和1000000），可能需要补齐位数。
- 负数处理：标准的基数排序不适用于负数，需要额外处理（如偏移量法）。
七、总结
基数排序是一种高效的非比较型排序算法，特别适合处理大量整数数据。它的核心思想是“按位分配，逐位排序”，通过多次分配和收集实现整体排序。虽然它有一定的局限性（仅适用于整数，空间消耗较大），但在合适的场景下，它的性能远超传统比较排序。
如果你经常处理大规模整数排序，不妨试试基数排序，或许会有意想不到的效果！
评论