基于桶的排序

一、桶排序：
本质是统计词频。
桶的数量要优先才可以。

如果不是数字而是对象的时候，需要用累加和统计数组来确定对应关系。
二、基数排序
按照个十百位依次进桶。

如果用队列来实现：

public class T9_Sort_Radix {
    public static void main(String[] args) {
        int [] arr = {103,102,101};
        process(arr);
    }
    public static int getMaxLen(int [] arr){
        int l = 1;
        int base = 10;
        for(int i = 0 ; i < arr.length ; i++){
            while(arr[i] /base > 0 ){
                l++;
                base *= 10;
            }
        }
        return l;
    }
    public static void process(int [] arr ){
        Queue<Integer> [] queues = new Queue[9];
        int maxLen = getMaxLen(arr);
        int divide = 1;
        for(int l = 1; l <=maxLen; l++){
            for(int i = 0 ; i < arr.length ; i ++){
                int bucket = arr[i] / divide % 10 ;
                if(queues[bucket] == null){
                    queues[bucket] = new LinkedList<>() ;
                }
                queues[bucket].add(arr[i] );
            }
            int cur = 0;
            for(int i  = 0; i < queues.length; i ++){
                while(queues[i] !=null && queues[i].size()>0 ){
                    arr[cur++] = queues[i].poll();
                }
            }
            divide *=10;
        }
        System.out.println(Arrays.toString(arr));
    }
}

step1: 找最大数有多少位，因为小的数前面要补0；
左程云的函数：
有点问题，如果最大数是0的话， 那么res就是0了，但实际0也是1位数。

申请桶

这个第几个桶，在申请额外桶空间的时候没有申请0～10个桶。其实是申请了10个桶，只不过使用累加次品表表示的
就是代码中的int[] count = new int[ radix]
注意：
1、j = getDigit(arr[i], d) 是求的当前位的数字，

2、他上面一行，是从右往左进行遍历的，这样能保证后面出现的依然在后面，(左程云：保证先入桶的先出)

实际上就是 桶排序的算法， 用一个count前缀和 模拟分片。

/**
 * @author 张伟-算法
 * @version 1.0
 * @date 2021/9/9 6:07 下午
 */
public class T8_Sort_Bucket {
    public static void main(String[] args) {
        int[] arr = {1,2,2,3,5,4,4};
        process(arr);
    }
    public static void process(int[]arr ){
        int max = arr[0];
        for(int i = 1; i<arr.length ; i ++){
            max = Math.max(max, arr[i]);
        }
        int[] buckets = new int [max + 1];
        for(int i = 0 ; i < arr.length ; i ++){
            buckets[arr[i]] ++;
        }
        /**累加桶数组*/
        for(int i = 1; i < buckets.length; i ++){
            buckets[i] = buckets[i] + buckets[i-1];
        }
        int [] res = new int [arr .length];
        for(int i = arr.lengh-1; i >= 0; i--){
            int no = arr[i];
            int chair = --buckets[no];
            res[chair] = no;
        }
        /**这里也可以把res的结果重新赋给arr，所以额外空间复杂度就是buckes的数量 + arr 的长度*/
        System.out.println(Arrays.toString(res));
    }
}