编辑代码

class Main {
public static int[] countingSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return arr;
        }

        // 找到数组中的最大值和最小值
        
        int minVal = arr[0];
        int maxVal = arr[0];

        for(int val:arr){
            if(minVal > val){ minVal = val; }
            if(maxVal < val){ maxVal = val; }
        }

        // 计算计数数组的长度并初始化计数数组
        int countLength = maxVal - minVal + 1;
        int[] count = new int[countLength];

        // 计算每个元素的频率
        for (int num : arr) {
            count[num - minVal]++;
        }

        // 根据频率重建排序后的数组
        int[] sortedArr = new int[arr.length];
        int index = 0;
        for (int i = 0; i < countLength; i++) {
            while (count[i] > 0) {
                sortedArr[index++] = i + minVal;
                count[i]--;
            }
        }

        return sortedArr;
    }

    public static void main(String[] args) {
   
        int[] arr1 = {4, 2, 7, 1, 5, 3,3,5,7};
        int[] sortedArr1 = countingSort(arr1);
        for(int val:sortedArr1){
            System.out.print(val+" ");
        }
    }
}