Java 实现基数排序算法 - 代码示例及解析

下面是使用 Java 实现基数排序（Radix Sort）的代码：

import java.util.Arrays;

public class RadixSort {
    public static void radixSort(int[] arr) {
        // 找到数组中最大的数，确定需要进行多少次基数排序
        int max = Arrays.stream(arr).max().getAsInt();
        
        // 对每个位数进行基数排序，从个位数开始到最高位数
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    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++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // 对 count 数组进行累加，得到每个数字在排序后的数组中的位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 从原数组中取出元素放入输出数组中，并更新 count 数组
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 将输出数组复制回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }

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

这段代码实现了基数排序算法。它首先找到数组中的最大值，确定了需要进行多少次基数排序（按位数排序）。然后，它使用计数排序作为基数排序的辅助排序算法，从最低位开始到最高位依次进行排序。最后，通过对每个位数进行排序，得到最终的排序结果。在 main 方法中，我们使用一些示例数据进行了测试，并输出排序结果。