public class CountSort {
    public static final int[] ARRAY = {2, 5, 3, 0, 2, 3, 0, 3};
    public static final int[] ARRAY2 = {95,93,92,94,92,93,95,90};
    //優(yōu)化前
    private static int[] sort(int[] array) {
        if (array.length < 2) return array;
        //找出數(shù)組的最大值
        int max = array[0];
        for (int i : array) {
            if (i > max) {
                max = i;
            }
        }
        //初始化一個計(jì)數(shù)數(shù)組且值為0
        int[] countArray = new int[max + 1];
        for (int i = 0; i < countArray.length; i++) {
            countArray[i] = 0;
        }
        //填充計(jì)數(shù)數(shù)組
        for (int temp : array) {
            countArray[temp]++;
        }
        int o_index = 0;//原數(shù)組下標(biāo)
        int n_index = 0;//計(jì)數(shù)數(shù)組下標(biāo)
        while (o_index < array.length) {
            //只要計(jì)數(shù)數(shù)組的下標(biāo)不為0，就將計(jì)數(shù)數(shù)組的值從新寫回原數(shù)組
            if (countArray[n_index] != 0) {
                array[o_index] = n_index;//計(jì)數(shù)數(shù)組下標(biāo)對應(yīng)元素組的值
                countArray[n_index]--;//計(jì)數(shù)數(shù)組的值要-1
                o_index++;
            } else {
                n_index++;//上一個索引的值為0后開始下一個
            }
        }
        return array;
    }
    //優(yōu)化后
    private static int[] sort2(int[] array) {
        if (array.length < 2) return array;
        //找出數(shù)組中的最大值和最小值
        int min = array[0], max = array[0];
        for (int i : array) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //定義一個偏移量,即最小值前面0~min的范圍,這里直接用一個負(fù)數(shù)來表示
        int bias = 0 - min;
        //初始化一個計(jì)數(shù)數(shù)組且值為0
        int[] countArray = new int[max - min + 1];
        for (int i = 0; i < countArray.length; i++) {
            countArray[i] = 0;
        }
        for (int temp : array) {
            countArray[temp + bias]++;
        }
        //填充計(jì)數(shù)數(shù)組
        int o_index = 0;//原數(shù)組下標(biāo)
        int n_index = 0;//計(jì)數(shù)數(shù)組下標(biāo)
        while (o_index < array.length) {
            if (countArray[n_index] != 0) {
                array[o_index] = n_index - bias;
                countArray[n_index]--;
                o_index++;
            } else {
                n_index++;
            }
        }
        return array;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
        System.out.println("=================優(yōu)化排序====================");
        print(ARRAY2);
        System.out.println("============================================");
        print(sort2(ARRAY2));
    }
}