计数排序

/**
 * 计数排序
 */
public class CountSort01 {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        //找出数组中最大的数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }

        //创建一个辅助数组
        int[] help = new int[max + 1];

        //遍历待排序的数组，值作为help数组的下标，help数组中的值+1
        for (int i = 0; i < arr.length; i++) {
            help[arr[i]]++;
        }

        //根据help数组，把数拷贝回原数组
        int index = 0;
        for (int i = 0; i < help.length; i++) {
            for (int j = 0; j < help[i]; j++) {
                arr[index++] = i;
            }
        }

    }

}

桶排序

/**
 * 桶排序：计数排序的一种应用
 */
public class CountSort02 {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        //取得当前数组最大值的位数
        int maxBit = getMaxBit(arr);

        //创建一个辅助数组
        int[] help = new int[arr.length];

        for (int i = 1; i <= maxBit; i++) {

            int[] count = new int[10];

            for (int j = 0; j < arr.length; j++) {
                //获取数组中每个值指定位上的数
                int bitNum = getBitNum(arr[j], i);
                //count数组此时记录指定数位上不同数字出现的次数
                count[bitNum]++;
            }

            for (int j = 1; j < count.length; j++) {
                //count数组变成指定数位上数字小于等于j的数的个数有几个
                count[j] += count[j - 1];
            }

            //根据count数组的记录，从原数组的最后一位往前遍历，放入help数组中的指定位置
            for (int j = arr.length - 1; j >= 0; j--) {
                int bitNum = getBitNum(arr[j], i);
                //count[bitNum]记录了当前数位i上数字小于等于bitNum的数，出现的次数
                //所以arr[j]放入到help数组中count[bitNum]-1的位置
                help[count[bitNum] - 1] = arr[j];
                //处理过了，减一，下次遇到指定数位上数字相同的数，就会放到前一个位置
                count[bitNum]--;
            }

            //help数组拷贝回原数组
            for (int j = 0; j < help.length; j++) {
                arr[j] = help[j];
            }

        }

    }

    private static int getBitNum(int num, int bit) {
        for (int i = 0; i < bit - 1; i++) {
            num /= 10;
        }
        int help = (num / 10) * 10;
        return num - help;
    }

    private static int getMaxBit(int[] arr) {
        //找出数组中最大的数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }

        int res = 0;
        while (max != 0) {
            max /= 10;
            res++;
        }

        return res;
    }

}

桶排序是计数排序的一种应用。从低数位开始直到高数位，每次遍历数组中的每一个数，以对应数位上的数作为下标，把当前数放入到该下标指定的队列中，然后在遍历每一个队列，弹出放回到原数组。
可以做出如下优化：
1、假设当前数位为d
2、遍历数组每一个数的d数位上的数，创建一个count数组，下标为d，记录d数位上的数出现的次数，count[i]此时就是d数位上的数位i的出现了几次
3、遍历count数组，累加前缀和，count[i]就是d数位上的数小于等于i的，出现了几次
4、创建一个help数组，从后往前遍历原数组，得出d数位上的数i，然后根据count[i]得知，d数位上的数小于等于i的有count[i]个，则在数组help下标为count[i]-1的位置放入当前遍历的数，然后count[i]减一，表示d数位上的数小于等于i的还剩count[i]-1个没处理