桶排序算法

算法简介

说到桶排序，它的思想就是把分治用到极致，把一个序列分为一个个桶，然后对每个桶进行排序，最后再进行整合。

算法描述

  1. 确定这个序列要分为几个桶
  2. 把每个元素放到对应的桶里面
  3. 对每个桶进行排序
  4. 对所有的桶进行整合

图解

倘若我有这样一个序列
桶1

现在我们要确定桶的数量，如和确定呢，这里面有一个计算公式

桶的数量 = （最大值 - 最小值）/ 数组长度 + 1

那这里面我们可以确定桶的数量为 49 / 13 +1 = 4；

现在我们再用另一个公式确定每个元素在哪个桶中

元素位置 =（ 元素大小 - 最小值）/ 数组长度

OK，根据这个公式我们可以确定每个元素都在第几个桶里面
桶2

现在再对每一个桶进行排序（这里面没有固定的排序算法）

桶3

对每个桶进行排序后最后我们进行整合，就变成了一个有序的序列。
桶4

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 function bucketSort(arr){
    let max = Math.max(...arr);
    let min = Math.min(...arr);
    let bucketNum = parseInt((max - min) / arr.length) + 1;

    let bucketArr = new Array(bucketNum);
    for(var i=0;i<bucketNum;i++){
        bucketArr[i] = new Array();
    }

    for(var i of arr){
        let num = parseInt((i-min) / arr.length);
        bucketArr[num].push(i);
    }
    for(var i of bucketArr){
        i.sort();
    }
    let k = 0;
    for(var i=0;i<bucketArr.length;i++){
        for(var j=0;j<bucketArr[i].length;j++){
            arr[k++] = bucketArr[i][j];
        }
    }
}


let arr = [1,20,31,58,46,5,6,7,21,32,44,59];
bucketSort(arr);
console.log(arr);

复杂度

平均时间复杂度：O(n + k)
最佳时间复杂度：O(n + k)
最差时间复杂度：O(n ^ 2)
空间复杂度：O(n * k)
稳定性：稳定

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。