桶排序是计数排序的升级版，弥补了计数排序的局限性

什么是桶排序

所谓桶(bucket)，就是一个区间范围，里边可以承载一个或者多个元素，

例如，有一个非整数数列，如下：

4.5， 0.84， 3.25， 2.18， 0.5

第一步，创建桶，并确定每一个桶的区间范围，

具体需要建立多少个桶，如何确立桶的区间范围，有很多种不同的实现方式，这里创建桶的数量等于原始数列的元素数量，除去最后一个桶只包含数列最大值外，前边各个桶的区间按照比例来确定

区间跨度 = (最大值 – 最小值)/(桶的数量 – 1)

第二步，遍历原始数组，把元素放入各个桶中

第三步，对每个桶内的元素分别进行排序

第四步，遍历所有桶，输出所有元素

实现代码

    function bucketSort(arr:Array<number>) {
        // 1. 找出最大值和最小值 并得出差值 d
        let max = arr[0];
        let min = arr[0];
        for (let index = 0; index < arr.length; index++) {
            if(arr[index] > max) {
                max = arr[index]
            }        
            if(arr[index] < min) {
                min = arr[index]
            }
        }
        const d = max - min;
    
    
        // 2. 初始化桶
        const bucketNum = arr.length;
        /*
            小坑：这样的写法会导致每个元素数组为同一个地址
            let bucketList = new Array(bucketNum).fill([])
        */ 
        let bucketList = new Array(bucketNum)
    
    
        for (let index = 0; index < bucketList.length; index++) {
            bucketList[index] = []
        }
    
    
        // 3. 遍历原始数组，将每个元素放入桶中
        let area = d/(bucketNum - 1);
        for (let index = 0; index < arr.length; index++) {
            let num = Math.floor((arr[index] - min)/area);
            bucketList[num].push(arr[index])      
        }
        /* 
            具体建立多少桶，和如何确定桶的区间范围有很多，
            这里实现的很巧妙：
                1. math.floor：
                    (元素-min)/area = 排在第几个桶，理论上来讲应该为 向上取整，但是数组下标从 0 所以为 math.floor
                2. bucketNum - 1:
                    由于 (最大值 - min)/area 一定为最后一个桶 且为整数，即：
                    d = max - min
                    area = d/num
                    result = (max - min)/area = (max - min)/d * num = (max - min)/(max - min) * num
                    result === num
    
    
                    但是由于数组下标为 0 开始 最后一个桶为 num - 1 
                    所以在计算 area时 为 d/(num - 1)
        */
    
    
        // 4. 每个桶内进行排序
        for (let index = 0; index < bucketList.length; index++) {
            bucketList[index] = bucketList[index].sort((a:number, b:number) => (a - b))        
        }
    
    
        // 拉平数组 输出
        return bucketList.flat()
    }
    
    
    function main() {
        let arr = [4.12, 6.412, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09, 10];
        console.log(bucketSort(arr))
    };
    main();
复制代码