s004-桶排序

概念

之前写的博客中讲述的排序算法，例如选择排序，冒泡排序，插入排序，快排，归并和堆排序都是基于比较的算法
而桶排序不是基于比较的算法，而是基于数据状态的算法
桶排序(Bucket sort)或者箱排序是一个排序算法，工作的原理是将数组分到有限的桶里。每个桶再个别排序（有可能再使用别的排序算法或者是以递归的方式继续使用桶排序进行排序）

计数排序

概念
计数排序：如果数组中数的范围控制在一定范围内，比如人的年龄数组，其值一定在0-200之间
那么我们可以准备一个长度为201的备用数组，初始值为0，遍历数组，将备用数组index值为年龄数组当前值的值++，即统计年龄数组的词频，最终按照备用数组中数据的词频，还原原数组，完成排序，复杂度是$O(N)$
计数排序的时间复杂度虽然低，但是可用范围比较窄，因为一般的排序都是在实数范围内的排序，范围比较大，使用计数排序得不偿失

基数排序

概念
基数排序：举例说明吧
例如[12,45,23,123,35]
由于数组中的数都是10进制的数，因此准备长度为10的桶
第一次按照个位数的值排序
index为2的桶 12
index为3的桶 23,123
index为5的桶 45,35
出桶，同一个桶先进先出[12,23,123,45,35]

第二次按照十位数的值排序
index为1的桶 12
index为2的桶 23,123
index为3的桶 35
index为5的桶 45
出桶，同一个桶先进先出[12,23,123,35,45]

第三次按照十位数的值排序
index为0的桶 12,23,35,45
index为1的桶 123
出桶[12,23,35,45,123]
排序完毕

基数排序升级版
举例说明
例如[12,45,23,123,35]
由于数组中的数都是10进制的数，因此准备长度为10的count数组[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
第一次按照个位数的值排序
count[0,0,1,2,0,2,0,0,0,0]个位数为2的值有1个，为3的有两个，为5的有两个
count累加[0,0,1,3,3,5,5,5,5,5]个位数为小于等于2的有1个，小于等于3的有3个，小于等于5的有5个
将[12,45,23,123,35]按照从右往左的顺序填入与该数组相同大小的备用数组中
对于35，个位数是5，小于等于5的数有5个，所以填入index为4的地方,小于等于5的数数量--，count累加[0,0,1,3,3,4,5,5,5,5]
对于123，个位数是3，小于等于3的数有3个，所以填入index为2的地方,小于等于3的数数量--，count累加[0,0,1,2,3,4,5,5,5,5]
对于23，个位数是3，小于等于3的数有2个，所以填入index为1的地方,小于等于3的数数量--，count累加[0,0,1,1,3,4,5,5,5,5]
对于45，个位数是5，小于等于5的数有4个，所以填入index为3的地方,小于等于3的数数量--，count累加[0,0,1,2,3,3,5,5,5,5]
对于12，个位数是2，小于等于2的数有1个，所以填入index为0的地方,小于等于2的数数量--，count累加[0,0,0,2,3,4,5,5,5,5]
备用数组[12,23,123,45,35]

第二次按照十位数的值排序
count[0,1,2,1,1,0,0,0,0,0]十位数为1的值有1个，为2的有两个，为3的有1个，为4的有1个
count累加[0,1,3,4,5,5,5,5,5,5]十位数为小于等于1的有1个，小于等于2的有3个，小于等于4的有4个，小于等于5的有5个
将[12,23,123,45,35]按照从右往左的顺序填入与该数组相同大小的备用数组中
对于35，十位数是3，小于等于3的数有4个，所以填入index为3的地方,小于等于3的数数量--，count累加[0,1,3,3,5,5,5,5,5,5]
对于45，十位数是4，小于等于4的数有4个，所以填入index为4的地方,小于等于4的数数量--，count累加[0,1,3,3,4,5,5,5,5,5]
对于123，十位数是2，小于等于2的数有3个，所以填入index为2的地方,小于等于2的数数量--，count累加[0,1,2,3,4,5,5,5,5,5]
对于23，十位数是2，小于等于2的数有2个，所以填入index为1的地方,小于等于2的数数量--，count累加[0,1,1,3,4,5,5,5,5,5]
对于12，十位数是1，小于等于1的数有1个，所以填入index为0的地方,小于等于1的数数量--，count累加[0,0,2,3,4,5,5,5,5,5]
备用数组[12,23,123,35,45]

第三次按照百位数的值排序
count[4,1,0,0,0,0,0,0,0,0]百位数为0的值有4个，为1的有1个
count累加[4,5,5,45,5,5,5,5,5,5]百位数为小于等于0的有4个，小于等于1的有5个
将[12,23,123,35,45]按照从右往左的顺序填入与该数组相同大小的备用数组中
不详细叙述啦，最终
备用数组[12,23,35,45,123]

实现

package com.kuang.example01;

/**
 * 功能描述
 *
 * @since 2022-10-29
 */
public class RadixSort {
    /**
     *
     * @param arr 待排序数组
     * @param l 数组待排序的左下标
     * @param r 数组待排序的右下标
     * @param digit 最大数的十进制位数，如100，digit为3,10000，digit为5
     */
    public void radixSort(int[] arr, int l, int r, int digit){
        // 基数设置为10，即待排序的数是几进制
        final int radix = 10;
        // 准备一个辅助空间
        int[] help = new int[r-l+1];
        for (int i = 1; i <= digit; i++) {
            int[] count = new int[10];
            for (int j = l; j <=r ; j++) {
                int value =  getDigit(arr[j],i);
                count[value]++;
            }
            for (int j = 1; j < count.length; j++) {
                count[j]+=count[j-1];
            }

            for (int j = r; j >=l ; j--) {
                int value =  getDigit(arr[j],i);
                help[count[value]-1] = arr[j];
                count[value]--;
            }

            for (int j = l; j < r-l+1; j++) {
                arr[j]=help[j];
            }
        }
    }

    public static int maxBits(int[] arr){
        int result=0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
        }

        while(max!=0){
            max /=10;
            result++;
        }
        return result;
    }

    public static int getDigit(int value, int d){
        return (value/((int)Math.pow(10,d-1)) %10);
    }

    public static void main(String[] args) {
        int[] arr ={10,45,36,87,123,456,34};
        int digit = maxBits(arr);
        RadixSort sort = new RadixSort();
        sort.radixSort(arr,0,6, digit);
        System.out.println(arr);

    }
}