排序-基数排序

基数排序（Radix Sort）是一种非比较性的排序算法，它将数据按照位数逐个分配到不同的桶中，从而实现排序。以下是一个基数排序的Java代码示例：

import java.util.Arrays;

public class RadixSort {

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        int max = Arrays.stream(arr).max().getAsInt();
        int exp = 1;

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

        Arrays.fill(count, 0);

        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        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};
        System.out.println("Original array: " + Arrays.toString(arr));
        
        radixSort(arr);
        
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

在这个示例中，radixSort 方法使用基数排序算法来对整数数组进行排序。首先，找到数组中的最大值以确定需要进行几轮排序（根据位数）。然后，通过 countingSortByDigit 方法对数组按照当前位上的数字进行计数排序。最后，将排序后的结果拷贝回原始数组。