算法简介

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

算法描述

具体算法描述如下：

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

代码实现

复制
1/*方法说明：桶排序
2@param  array 数组
3@param  num   桶的数量*/
4function bucketSort(array, num) {
5    if (array.length <= 1) {
6        return array;
7    }
8    var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0;
9    num = num || ((num > 1 && regex.test(num)) ? num : 10);
10    console.time('桶排序耗时');
11    for (var i = 1; i < len; i++) {
12        min = min <= array[i] ? min : array[i];
13        max = max >= array[i] ? max : array[i];
14    }
15    space = (max - min + 1) / num;
16    for (var j = 0; j < len; j++) {
17        var index = Math.floor((array[j] - min) / space);
18        if (buckets[index]) {   //  非空桶，插入排序
19            var k = buckets[index].length - 1;
20            while (k >= 0 && buckets[index][k] > array[j]) {
21                buckets[index][k + 1] = buckets[index][k];
22                k--;
23            }
24            buckets[index][k + 1] = array[j];
25        } else {    //空桶，初始化
26            buckets[index] = [];
27            buckets[index].push(array[j]);
28        }
29    }
30    while (n < num) {
31        result = result.concat(buckets[n]);
32        n++;
33    }
34    console.timeEnd('桶排序耗时');
35    return result;
36}
37var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
38console.log(bucketSort(arr,4));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

算法分析

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

• 最佳情况：T(n) = O(n+k)
• 最差情况：T(n) = O(n+k)
• 平均情况：T(n) = O(n2)