排序算法之8：计数排序 CountSort

基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。

public class CountSort {
    public static void countSort(int[] arr) {
        if (arr == null || arr.length == 0)
            return;

        int max = max(arr); //寻找数组中最大值

        int[] count = new int[max + 1]; //建立临时数组, 长度为max+1
        Arrays.fill(count, 0);  //使用0填充数组中的元素

        //使用待排序数组的元素作为临时数组的下标，并且统计每个元素的个数
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]] = count[arr[i]] + 1; 
        }

        
        int arrIndex = 0;
        for (int i = 0; i <= max; i++) {    //从0到max挨个遍历
            //遍历临时数组某下标对应的数组元素值，数组元素值代表下标值出现了几次，依次添加到目标数组
            for (int j = 0; j < count[i]; j++) {    
                arr[arrIndex++] = i; 
            }
        }
    }

    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int ele : arr) {
            if (ele > max)
                max = ele;
        }

        return max;
    }
}