public class CountingSort {
    private static int[] countingSort(int[] arr) {
        //1、求取最大值和最小值，計(jì)算中間數(shù)組的長(zhǎng)度：中間數(shù)組是用來記錄原始數(shù)據(jù)中每個(gè)值出現(xiàn)的頻率
        int min = arr[0], max = arr[0];
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
 
        //2、有了最大值和最小值能夠確定中間數(shù)組的長(zhǎng)度
        //例如存儲(chǔ) 5-0+1=6
        int[] countArray = new int[max - min + 1];
 
        //3、循環(huán)遍歷舊數(shù)組計(jì)數(shù)排序: 就是統(tǒng)計(jì)原始數(shù)組值出現(xiàn)的頻率到中間數(shù)組B中
        for (int i : arr) {
            countArray[i - min] += 1; //數(shù)的位置上+1
        }
 
        //4、統(tǒng)計(jì)數(shù)組做變形，后邊的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }
 
        //5、倒序遍歷原始數(shù)組，從統(tǒng)計(jì)數(shù)組中找到正確的位置，輸出到結(jié)果數(shù)組
        int[] resultArray = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            //給resultArray的當(dāng)前位置賦值
            resultArray[countArray[arr[i] - min] - 1] = arr[i];
            //給countArray的位置的值--
            countArray[arr[i] - min]--;
        }
        return resultArray;
    }
 
    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        int[] sortedArr = countingSort(arr);
        System.out.println(Arrays.toString(sortedArr));
    }
}