public class CountSort {
	private static int[] countSort(int[] array,int k) {
        int sum = 0;
        int B[] = new int[array.length]; // 最终用于返回的数组
        int C[] = new int[k + 1]; // 用于过渡的数组
        // 接下来我需要通过for循环遍历,得到每个元素在array里面出现的次数
        for(int i = 0; i < array.length; i++) {
            // 记住：array数组中的元素是 C 数组的下标
            // array[i]肯定是存在的,所以默认有一个,至于有多少个,通过遍历不断 +1 即可
            // 比如这里array[0]是2,但是array[4]也是2.所以这里 array[0] == array[4] == 2,
            // 意味着 C[2] 出现两次,所以 C[2] = 2,所以每当出现过相同的array[i]时就 +1
            C[array[i]] += 1; 
        }
        // 这里面有一个巧妙的思路就是利用数组下标,他会自动帮我们排序,毕竟数值是C数组的下标。
        // 这个时候我该考虑怎么把数据从 C 数组中取出来放到 B 数组了
        for(int i = 0; i < k + 1; i++) {
            // 这时候的 C[i], i 其实是 array里面的元素, C[i] 其实是该元素的个数
            // i 从0开始递增到 k 即最大值,但是,我能保证i包含 0~k中所有的数值吗？
            // 对不起,我不能保证！！！
            // 但是,不用担心！编译器会自动帮我们把数组中没有值的但是却必须存在的下标对应的值初始化为 0
            if(C[i] != 0) { // 代表存在该值
                int x = C[i]; // 过渡下
                // 由于C[i] 其实对应的是 A 数组里相同数据存在的个数,那么我只需对个数遍历即可。
                // 但是我这里又困住了,第一轮循环从 0 开始确立前几个数组元素是没问题的,比如第一次遍历的是数值为0的个数并进行赋值
                // 关键问题是当第二轮循环,开始遍历数值为2的个数进行赋值时,我不可能继续从B[0]开始
                // 我应该紧接着上一轮循环后的下标开始,所以这里我需要引入一个变量 sum
                for(int j = 0; j < x; j++) {
                    // 这里一开始我写的是B[j] = i,经过实践发现这是不对的,后来我意识到了不能每次都从0开始,
                    // 就改成了 B[sum + j] = i,依然是错误的。因为sum++不断自增,最终sum是会跟array.length相等,加上j就明显超过数组长度了
                    // 我也尝试修改 j < x+sum,继续打了脸,这里的 x 再三强调是相同数值的个数,我不能凭空给它增加啊
                    B[sum] = i; 
                    sum++;
                }
            }
        }
        return B;
    }
    public static void main(String[] args) {
        int[] A = new int[]{2,5,3,0,2,3,0,3};
        int[] B = countSort(A, 5);
        for(int i = 0; i < B.length; i++) {
        	System.out.println("B[" + i + "] = " + B[i]);
        }
    }
}

package com.lizz.set;
public class CountSort {
	private static int[] countSort(int[] array,int k) {
        int[] C = new int[k+1]; // 构造C数组
        int length = array.length, sum = 0; // 获取A数组大小用于构造B数组  
        int[] B = new int[length]; // 构造B数组
        for(int i = 0; i < length; i++) {
            C[array[i]] += 1; // 统计A中各元素个数，存入C数组
        }
        for(int i = 0; i < k+1; i++) { // 修改C数组
            System.out.println(C[i]);
            sum += C[i];
            C[i] = sum;    
            // System.out.println(C[i]);
        }
        for(int i = length-1; i >= 0; i--) { // 遍历A数组，构造B数组
            B[C[array[i]]-1] = array[i]; // 将A中该元素放到排序后数组B中指定的位置
            C[array[i]]--; // 将C中该元素-1，方便存放下一个同样大小的元素
        }
        return B; // 将排序好的数组返回，完成排序
    }
    public static void main(String[] args) {
        int[] A = new int[]{2,5,3,0,2,3,0,3};
        int[] B = countSort(A, 5);
        for(int i = 0; i < A.length; i++) {
            System.out.println((i+1) + "th:" + B[i]);
        }
    }
}
1th:0
2th:0
3th:2
4th:2
5th:3
6th:3
7th:3
8th:5