基数排序
基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是按照低位先排序，然后收集；再按高位排序，然后再收集；依次类推，直到最高位。基数排序通常使用计数排序（Counting Sort）作为子程序来实现。
基数排序适用于整数排序，尤其是当整数范围较小时特别有效。它的时间复杂度为 O(nk)，其中 n 是待排序的元素数量，k 是整数的最大位数。在某些情况下，基数排序可以比基于比较的排序算法（如快速排序或归并排序）更高效。例如，在处理邮政编码、电话号码等固定长度的整数时，基数排序是一个非常好的选择。
基本思想
基数排序的核心思想是将整数按位数分解，然后对每一位进行排序。通常，从最低位（个位）开始排序，一直到最高位（最高位取决于整数的最大值）。具体步骤如下：
- 确定整数的最大位数：找出待排序数组中的最大值，从而确定整数的最大位数。
- 按位排序：从最低位开始，使用计数排序或其他稳定的排序算法对每一位进行排序。
- 重复步骤2：对每一位进行排序，直到最高位为止。
计数排序
计数排序是一种线性时间复杂度的排序算法，适用于整数排序。它是基数排序的一个重要组成部分，用于对整数的每一位进行排序。计数排序的基本思想是统计每个整数出现的次数，然后根据统计结果生成排序后的数组。
代码实现
查看代码
java
import java.util.Arrays;
public class RadixSort {
// 辅助方法：获取整数的最大位数
private static int getMaxDigits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int num : arr) {
max = Math.max(max, num);
}
return (int) (Math.log10(max) + 1);
}
// 计数排序：针对某一位进行排序
private static void countingSort(int[] arr, int exp) {
int output[] = new int[arr.length];
int count[] = new int[10];
// 初始化计数数组
Arrays.fill(count, 0);
// 存储每个数字出现的次数
for (int i = 0; i < arr.length; i++) {
int index = (arr[i] / exp) % 10;
count[index]++;
}
// 更新计数数组，使count[i]包含的是小于或等于i的元素的数量
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 构建输出数组
for (int i = arr.length - 1; i >= 0; i--) {
int index = (arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
// 复制输出数组到原数组
System.arraycopy(output, 0, arr, 0, arr.length);
}
// 基数排序
public static void sort(int[] arr) {
int maxDigits = getMaxDigits(arr);
for (int exp = 1; maxDigits > 0; exp *= 10, maxDigits--) {
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);
sort(arr);
System.out.println("排序后的数组:");
printArray(arr);
}
}代码解释
- getMaxDigits 方法：计算数组中最大值的位数。
- countingSort 方法：这是一个计数排序的实现，用于对数组的某一位进行排序。它首先统计每个数字出现的次数，然后根据统计结果生成排序后的数组。
- sort 方法：这是基数排序的核心方法。它首先计算数组中最大值的位数，然后从最低位开始逐位进行排序，直到最高位。
时间复杂度
基数排序的时间复杂度为
空间复杂度
基数排序的空间复杂度为