编辑代码

import java.util.Arrays;

public class LinearCountingSort {
    public static void main(String[] args) {
        int[] arr = {4, 2, 7, 1, 3, 7, 9};
        linearCountingSort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(arr));
    }

    public static void linearCountingSort(int[] arr) {
        int min = Arrays.stream(arr).min().orElse(0);
        int max = Arrays.stream(arr).max().orElse(0);

        int range = max - min + 1;

        int[] countArray = new int[range];
        int index = 0;

        // 统计元素出现的次数
        for (int value : arr) {
            countArray[value - min]++;
        }

        // 构建排序数组
        for (int i = 0; i < range; i++) {
            while (countArray[i] > 0) {
                arr[index++] = i + min;
                countArray[i]--;
            }
        }
    }
}