编辑代码

class Main {
    public static void main(String[] args) {
        int[] arr = {4, 2, 5, 1, 3, 5, 4, 2, 3, 1};
        int[] sortedArr = linearCountingSort(arr, 5);
        for (int num : sortedArr) {
            System.out.print(num + " ");
        }
    }
    public static int[] linearCountingSort(int[] arr, int max) {
        int[] countArr = new int[max + 1];
        int[] sortedArr = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }
        for (int i = 1; i < countArr.length; i++) {
            countArr[i] += countArr[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            sortedArr[countArr[arr[i]] - 1] = arr[i];
            countArr[arr[i]]--;
        }
        return sortedArr;
    }
}