排序算法之基数排序详细解读（附带Java代码解读）

基数排序（Radix Sort）是一种非比较型的排序算法，它通过逐位（或逐字节）的排序来完成对整个数据集的排序。与其他排序算法不同，基数排序并不直接比较元素的大小，而是将元素按位分组，依次进行排序。

算法思想

基数排序的基本思想是将待排序的元素按位分开，从最低位到最高位（或相反），分别对这些位进行排序。排序时通常使用稳定的排序算法（如计数排序）来保证相同位的元素保持原有的顺序。基数排序分为两种主要方法：从最低有效位（LSD）排序和从最高有效位（MSD）排序。

1. 从最低有效位（LSD）排序

这种方法从最低有效位（即数字的个位）开始排序，然后逐步向更高位（如十位、百位）推进，直到最高有效位。最常见的基数排序就是LSD排序。

2. 从最高有效位（MSD）排序

这种方法从最高有效位（即数字的最高位）开始排序，然后逐步向更低位推进。MSD排序通常用于字符串排序或对数值排序要求较高的场景。

过程示例

以从最低有效位（LSD）排序为例，假设有一个待排序的数组：[170, 45, 75, 90, 802, 24, 2, 66]

步骤 1: 从最低有效位开始

1. 排序个位：

   • 170 → 0
   • 45 → 5
   • 75 → 5
   • 90 → 0
   • 802 → 2
   • 24 → 4
   • 2 → 2
   • 66 → 6

   排序后数组：[170, 90, 802, 2, 24, 45, 75, 66]

2. 排序十位：

   • 170 → 7
   • 90 → 9
   • 802 → 0
   • 2 → 0
   • 24 → 2
   • 45 → 4
   • 75 → 7
   • 66 → 6

   排序后数组：[802, 2, 24, 45, 66, 75, 170, 90]

3. 排序百位：

   • 802 → 8
   • 2 → 0
   • 24 → 0
   • 45 → 0
   • 66 → 0
   • 75 → 0
   • 170 → 1
   • 90 → 0

   排序后数组：[170, 24, 45, 66, 75, 90, 802]

最终排序后的数组为：[2, 24, 45, 66, 75, 90, 802]

算法复杂度

• 时间复杂度:

  • 最坏情况: O(n * k)
  • 平均情况: O(n * k)
  • 最佳情况: O(n * k)

  其中，n 是元素的数量，k 是每个元素的位数（或字节数）。

• 空间复杂度: O(n + k) 需要额外的存储空间用于计数排序。

优点

1. 稳定排序：基数排序可以使用稳定的排序算法（如计数排序）来确保相同值的元素相对顺序不变。
2. 线性时间复杂度：对于固定范围的整数，基数排序的时间复杂度接近 O(n)，相较于比较型排序算法有很大优势。

缺点

1. 空间复杂度高：需要额外的存储空间来存储计数数组。
2. 适用范围有限：主要适用于整数排序或字符串排序，且对数值范围有一定要求。

Java代码解读

import java.util.Arrays;

public class RadixSort {

    // 主方法：执行基数排序
    public static void radixSort(int[] arr) {
        if (arr.length == 0) return;

        // 1. 找到最大值，确定最大位数
        int max = Arrays.stream(arr).max().getAsInt();
        int exp = 1; // 从个位开始排序

        // 2. 按位进行排序
        while (max / exp > 0) {
            countingSortByDigit(arr, exp);
            exp *= 10;
        }
    }

    // 按特定位进行计数排序
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // 1. 计算每个位的频率
        Arrays.fill(count, 0);
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // 2. 累计频率
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 3. 从后往前填充输出数组
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // 4. 复制输出数组到原数组
        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("排序前的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        radixSort(arr);

        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码说明

1. radixSort方法:

   • radixSort 方法找到数组中的最大值，并确定排序的最大位数。
   • 从个位开始进行排序，逐步增加到更高的位数（十位、百位等）。

2. countingSortByDigit方法:

   • countingSortByDigit 方法按照指定的位进行计数排序。
   • 使用 count 数组来统计每个数字出现的频率，并累积频率来确定元素的位置。
   • 将排序后的结果复制回原数组。

3. main方法:

   • 创建一个待排序的数组 arr。
   • 调用 radixSort 方法对数组进行排序。
   • 输出排序前和排序后的数组。