编辑代码

public class Main {  
    // 计数排序  
    public static void countingSort(int[] arr) {  
        int max = arr[0];  
        for (int i = 1; i < arr.length; i++) {  
            if (arr[i] > max) {  
                max = arr[i];  
            }  
        }  
        int[] count = new int[max + 1];  
        for (int i = 0; i < arr.length; i++) {  
            count[arr[i]]++;  
        }  
        for (int i = 0, j = 0; i <= max; i++) {  
            while (count[i] > 0) {  
                arr[j++] = i;  
                count[i]--;  
            }  
        }  
    }  
      
    // 线性计数排序  
    public static void linearCountingSort(int[] arr) {  
        int max = arr[0];  
        for (int i = 1; i < arr.length; i++) {  
            if (arr[i] > max) {  
                max = arr[i];  
            }  
        }  
        int[] count = new int[max + 1];  
        for (int num : arr) {  
            count[num]++;  
        }  
        int index = 0;  
        for (int i = 1; i <= max; i++) {  
            while (count[i] > 0) {  
                arr[index++] = i;  
                count[i]--;  
            }  
        }  
    }  
      
    public static void main(String[] args) {  
        int[] arr = {4, 2, 1, 5, 3};  
        System.out.println("Original array: ");  
        for (int num : arr) {  
            System.out.print(num + " ");  
        }  
        System.out.println();  
        countingSort(arr);  
        System.out.println("Sorted array by counting sort: ");  
        for (int num : arr) {  
            System.out.print(num + " ");  
        }  
        System.out.println();  
        linearCountingSort(arr);  
        System.out.println("Sorted array by linear counting sort: ");  
        for (int num : arr) {  
            System.out.print(num + " ");  
        }  
    }  
}