基数排序是一种非比较排序算法，利用元素的数字或字符的位数来排序。它通过逐位对数据进行排序，从最低有效位到最高有效位（或相反）依次进行，直到整个数组有序。基数排序通常用于对整数或字符串进行排序。

工作原理

基数排序将要排序的数字或字符串看作由多个“位”组成（如十进制数的个位、十位、百位，或者字符串的每个字符），然后依次对每一位进行排序。它本质上是基于桶排序（Bucket Sort）或计数排序（Counting Sort）的稳定排序。

基数排序的过程可以分为两种方法：

• LSD（Least Significant Digit）：从最低有效位开始排序。
• MSD（Most Significant Digit）：从最高有效位开始排序。

常见实现是 LSD 基数排序。

基数排序的步骤

以 LSD 基数排序为例，排序一个整数数组：

1. 确定位数：确定数组中最大的数的位数，这将决定排序的次数。
2. 按位排序：从最低有效位（个位）开始，依次对每一位进行稳定排序（通常使用计数排序或桶排序作为子过程）。排序结束后，下一位将包含前一位排序的结果。
3. 重复过程：重复步骤2，直到所有位都排序完毕，最终数组有序。

基数排序的示例

假设要对一组三位数的整数数组 [170, 45, 75, 90, 802, 24, 2, 66] 进行排序。具体步骤如下：

1. 按个位数排序：

[170, 90, 802, 2, 24, 45, 75, 66]

（个位：0、0、2、2、4、5、5、6）

2. 按十位数排序：

[802, 2, 24, 45, 66, 170, 75, 90]

（十位：0、0、2、4、6、7、7、9）

3. 按百位数排序：

[2, 24, 45, 66, 75, 90, 170, 802]

（百位：0、0、0、0、0、0、1、8）

Java 实现基数排序

import java.util.Arrays;public class RadixSort {// 获取数组中最大值的位数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;}// 对数组arr的d位数进行计数排序private static void countingSort(int[] arr, int exp) {int n = arr.length;int[] output = new int[n]; // 用于存储排序结果int[] count = new int[10]; // 用于存储每个数字的频率// 计算各个数字出现的频率for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}// 计算各个位置的累计频率for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 根据当前位数，将数字放到正确位置for (int i = n - 1; i >= 0; i--) {int index = (arr[i] / exp) % 10;output[count[index] - 1] = arr[i];count[index]--;}// 将结果复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}}// 基数排序主函数public static void radixSort(int[] arr) {// 找到最大数，确定最高位数int max = getMax(arr);// 对每个数位进行计数排序，exp是对应位数（1 -> 个位，10 -> 十位，100 -> 百位）for (int exp = 1; max / exp > 0; exp *= 10) {countingSort(arr, exp);}}// 打印数组public static void printArray(int[] arr) {for (int value : arr) {System.out.print(value + " ");}System.out.println();}// 测试基数排序public static void main(String[] args) {int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};System.out.println("原始数组:");printArray(arr);radixSort(arr);System.out.println("排序后的数组:");printArray(arr);}
}

输出结果

原始数组:
170 45 75 90 802 24 2 66 
排序后的数组:
2 24 45 66 75 90 170 802 

基数排序的时间和空间复杂度

时间复杂度：

基数排序的时间复杂度为 O(d * (n + k))，其中 n 是数组的长度，d 是数字中的最大位数，k 是每一位的取值范围（通常为10，即十进制数）。
在大多数情况下，d 是常数，所以基数排序的时间复杂度近似为 O(n)。

空间复杂度：

基数排序需要额外的空间来存储计数数组和输出数组，空间复杂度为 O(n + k)。

基数排序的优缺点

优点

• 线性时间复杂度：基数排序在特定情况下可以达到线性时间复杂度 O(n)，比许多比较排序算法（如快速排序）的平均时间复杂度 O(n log n) 更优。
• 稳定性：基数排序是稳定的，前一位的排序结果在下一位排序中不会改变。

缺点

• 空间复杂度较高：基数排序需要额外的空间来存储中间结果，空间复杂度较高，尤其在处理大数据时。
• 限制应用场景：基数排序适合数值或字符串等可以按位操作的数据，不适合复杂数据类型。
• 需要稳定的子排序算法：基数排序依赖于子排序算法（如计数排序）的稳定性。

基数排序的应用场景

• 排序大规模的整数数据：尤其是位数不多且取值范围有限的情况。
• 字符串排序：可以按字符位来排序，比如用于处理固定长度的字符串。
• 图像处理中的颜色排序：基数排序可用于按色彩通道分量进行排序。

基数排序与其他排序的对比

• 与比较排序的对比：与比较排序（如快速排序、归并排序）不同，基数排序不依赖于元素之间的比较，因此时间复杂度不受 O(n log n) 的下限约束。
• 与桶排序和计数排序的关系：基数排序可以看作是基于桶排序和计数排序的一种多次应用。每次处理一位元素，利用计数排序的稳定性确保排序结果正确。

总结

基数排序是一种高效的线性时间排序算法，尤其适合对整数和字符串数据进行排序。尽管它的空间复杂度较高，应用场景较为特定，但在处理大量数据且位数不多的情况下，它是一种优于比较排序的选择。