算法基础入门——计数排序、基数排序

package com.zuoshen.jichurumen.class03;

/**
 * @author ShiZhe
 * @create 2022-02-25 11:11
 */
public class code01 {

    /**
     * 计数排序
     * 当输入的元素是n个0到k之间的整数时，它的运行时间是Θ(n+k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
     * 一般适用于值在0-200之间的数组排序
     * @param arr
     */
    public static void countSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        // 获取待排序数组的最大值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // 建立辅助数组
        int[] bucket = new int[max + 1];
        // 将待排序数组按照数值填充进辅助数组
        for (int j = 0; j < arr.length; j++) {
            bucket[arr[j]]++;
        }
        int i = 0;
        for (int j = 0; j <bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }

    /**
     * 基数排序
     * 将整数按位数切割成不同的数字，然后按每个位数分别比较。
     * @param arr
     */
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 获取待排序数组的最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i <arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // 获取待排序数组最大值的位数
        int digit = 0;
        while (max != 0) {
            max /= 10;
            digit++;
        }

        // 规定基数为10，0-9
        final int radix = 10;

        // 新建辅助数组
        int[] bucket = new int[arr.length + 1];

        int i = 0, j = 0;

        // 循环次数为位数大小
        for (int d = 1; d <= digit; d++) {
            // 新建对应基数的数组
            int[] count = new int[radix];
            // 得到对应的基数数组中符合该基数的大小
            for (i = 0; i < arr.length; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            // 将基数数组相邻相加，得到按照基数排列下标个数，从下标为1开始相加
            // 例如：个位为1的有2个，个位为2的有3个，相加后，基数数组为[2.5]，表明0-1是个位为1,0-4是个位为1-2。
            for (i = 1; i < count.length; i++) {
                count[i] = count[i - 1] + count[i];
            }
            // 倒序遍历待排序数组，为了保持排序的稳定性
            for (i = arr.length -1 ; i >= 0; i--) {
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            // 复制给arr
            for (i = 0; i < arr.length ;i++) {
                arr[i] = bucket[i];
            }
        }
    }

    /**
     * 获得数据中的某一位
     * @param x
     * @param d
     * @return
     */
    public static int getDigit(int x, int d) {
        // Math.pow(a,b)表示a的b次方幂，Math.pow(2,3)则为2的3次方等于8
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }

    public static void main(String[] args) {
        // 计数排序
        int[] arr1 = {45, 4563, 14512, 222, 225, 24, 215, 45, 56315, 4534};
        countSort(arr1);
        for (int i = 0; i < arr1.length; i++) {
            System.out.println(arr1[i]);
        }
        // 基数排序
        int[] arr2 = {45, 4563, 14512, 222, 225, 24, 215, 45, 56315, 4534};
        radixSort(arr2);
        for (int i = 0; i < arr2.length; i++) {
            System.out.println(arr2[i]);
        }
    }
}