[排序算法]基数排序

1.基本思想

2.基数排序的步骤

LSD 基数排序的基本步骤：

3.基数排序算法的实现

4.时间复杂度分析

5.总结

PS：如有错漏之处，敬请指正

1.基本思想

基数排序（Radix Sort）是一种非比较性的整数排序算法，它根据数字的每一位来进行排序。基数排序的实现可以分为 LSD（Least Significant Digit）和 MSD（Most Significant Digit）两种方式。这里我将介绍 LSD 的基数排序算法的 Java 实现。

2.基数排序的步骤

基数排序（Radix Sort）是一种非比较性的整数排序算法，它根据数字的每一位来进行排序。基数排序的基本步骤如下：

确定排序的位数： 首先确定待排序数组中最大元素的位数，通常使用最高位数来确定排序的轮数。
按位排序： 从最低位开始，按照个位、十位、百位等顺序，对待排序数组进行稳定的排序（通常使用计数排序或桶排序）。
重复排序过程： 重复按位排序的过程，直到对数组中所有位数进行排序为止。
合并结果： 经过多轮按位排序后，数组变成有序的。

基数排序的实现可以分为 Least Significant Digit (LSD) 和 Most Significant Digit (MSD) 两种方式。LSD 从最低位开始排序，而 MSD 则从最高位开始排序。

LSD 基数排序的基本步骤：

初始化： 找到数组中最大的数字，确定需要排序的轮数。
按位排序：
- 从最低位开始，对所有元素按照当前位进行稳定的排序（通常使用计数排序）。
- 依次对个位、十位、百位等进行排序，直到最高位。
重复排序过程： 重复按位排序的过程，直到对数组中所有位数进行排序为止。
合并结果： 经过多轮按位排序后，数组变成有序的。

3.基数排序算法的实现

以下是LSD 基数排序算法 Java 的具体实现：

import java.util.Arrays;

public class RadixSort {

    // 获取数组中最大值
    public 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;
    }

    // LSD 基数排序
    public static void radixSort(int[] arr) {
        int max = getMax(arr);
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    // 计数排序
    public static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];
        Arrays.fill(count, 0);

        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]--;
        }

        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("Original Array: " + Arrays.toString(arr));

        radixSort(arr);
        
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

在上面的示例中，radixSort 方法用于执行基数排序，getMax 方法用于获取数组中的最大值，而 countingSort 方法则实现了计数排序的过程。基数排序的时间复杂度为 O(d*(n+b))，其中 d 是数字的位数，n 是数组的长度，b 是基数（这里是 10，因为使用十进制数进行排序）。

这是一个简单的基数排序的 Java 实现，你可以根据需要进行调整和扩展。