简介
基数排序是一种非比较型整数排序算法，其原理是按照低位先排序，然后收集，再按照高位排序，再收集，依次类推，直到最高位。这种方法可以视为对每个位上的数字进行稳定的排序。
算法步骤
- 确定最大数的位数。
- 对每一位进行排序：
- 从最低位开始，使用稳定的排序算法（如计数排序）对当前位进行排序。
- 排序完成后，将数组元素收集回原数组。
- 重复步骤2，直到最高位排序完成。
//countingSortByDigit 方法是计数排序的变种，用于对数组的每一位进行排序。
//radixSort 方法是基数排序的主方法，它首先找到最大数以确定最大位数，然后对每一位调用计数排序方法。
//main 方法中，我们初始化一个数组，然后调用 radixSort 方法进行排序，并打印排序后的结果。
public class RadixSort {
// 计数排序辅助方法
private static void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// 初始化计数数组
Arrays.fill(count, 0);
// 统计每个数字的当前位（exp位）出现的次数
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--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// 将输出数组复制回原数组
System.arraycopy(output, 0, arr, 0, n);
}
// 基数排序主方法
public static void radixSort(int[] arr) {
// 找到最大数，确定最大位数
int max = Arrays.stream(arr).max().getAsInt();
int exp = 1; // 初始为最低位
// 对每一位进行排序
while (max / exp > 0) {
countingSortByDigit(arr, exp);
exp *= 10;
}
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
// 打印排序后的数组
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}优点
- 稳定性：基数排序是稳定的排序算法，相等元素的相对位置不会改变。
- 线性时间复杂度：对于大数据集，基数排序的时间复杂度可以接近O(n)，特别是当数字的位数d较小时。
- 适用性：适用于数字排序，特别是当数字的位数固定时。
缺点
- 空间复杂度：基数排序需要额外的存储空间来存储排序过程中的临时数组，空间复杂度为O(n+k)，其中k是基数。
- 效率依赖：当数字的位数d较大时，效率会降低。
- 实现复杂性：相比于其他排序算法，基数排序的实现较为复杂。
时间复杂度和空间复杂度分析
- 时间复杂度：O(d*(n+b))，其中d是最大数的位数，n是数组长度，b是基数（通常是10）。
- 空间复杂度：O(n+k)，需要额外的存储空间来存储临时数组。
使用场景
- 当需要对大量数字进行排序，且这些数字的位数是固定的或相对较小时。
- 在需要稳定排序的场景下，基数排序是一个好选择。