什么是桶排序

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

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

4.5， 0.84， 3.25， 2.18， 0.5

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

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

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

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

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

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

实现代码

1    function bucketSort(arr:Array<number>) {
2        // 1. 找出最大值和最小值 并得出差值 d
3        let max = arr[0];
4        let min = arr[0];
5        for (let index = 0; index < arr.length; index++) {
6            if(arr[index] > max) {
7                max = arr[index]
8            }        
9            if(arr[index] < min) {
10                min = arr[index]
11            }
12        }
13        const d = max - min;
14    
15    
16        // 2. 初始化桶
17        const bucketNum = arr.length;
18        /*
19            小坑：这样的写法会导致每个元素数组为同一个地址
20            let bucketList = new Array(bucketNum).fill([])
21        */ 
22        let bucketList = new Array(bucketNum)
23    
24    
25        for (let index = 0; index < bucketList.length; index++) {
26            bucketList[index] = []
27        }
28    
29    
30        // 3. 遍历原始数组，将每个元素放入桶中
31        let area = d/(bucketNum - 1);
32        for (let index = 0; index < arr.length; index++) {
33            let num = Math.floor((arr[index] - min)/area);
34            bucketList[num].push(arr[index])      
35        }
36        /* 
37            具体建立多少桶，和如何确定桶的区间范围有很多，
38            这里实现的很巧妙：
39                1. math.floor：
40                    (元素-min)/area = 排在第几个桶，理论上来讲应该为 向上取整，但是数组下标从 0 所以为 math.floor
41                2. bucketNum - 1:
42                    由于 (最大值 - min)/area 一定为最后一个桶 且为整数，即：
43                    d = max - min
44                    area = d/num
45                    result = (max - min)/area = (max - min)/d * num = (max - min)/(max - min) * num
46                    result === num
47    
48    
49                    但是由于数组下标为 0 开始 最后一个桶为 num - 1 
50                    所以在计算 area时 为 d/(num - 1)
51        */
52    
53    
54        // 4. 每个桶内进行排序
55        for (let index = 0; index < bucketList.length; index++) {
56            bucketList[index] = bucketList[index].sort((a:number, b:number) => (a - b))        
57        }
58    
59    
60        // 拉平数组 输出
61        return bucketList.flat()
62    }
63    
64    
65    function main() {
66        let arr = [4.12, 6.412, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09, 10];
67        console.log(bucketSort(arr))
68    };
69    main();
70

小结

时间复杂度：

1. 求数列最大最小值，运算量为 n

2. 创建空桶，运算量为 n

3. 把原始数组的元素分配到桶中，运算量为 n

4. 在每个桶内部做排序，在元素分布相对均匀的情况下，所有桶的运算量之和为 n

5. 输出排序数列，运算量为 n

因此时间复杂度为 O(n)

空间复杂度为 O(n)

问题：

1. 在额外空间充足的情况下，为了性能，尽量增大桶的数量

2. 桶排序性能并非绝对稳定，如果元素的分布极不均匀，在极端情况下，一个桶中有 n - 1 个元素，最后一个桶中有 1 个元素，则时间复杂度将退化为 O(nlogn)，而且还白白创建了许多空桶

摘要总结自: 漫画算法小灰的算法之旅