Back
To Top
桶排序
桶排序（Bucket Sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
为了使桶排序更加高效，我们需要做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
算法原理
- 设置一个定量的数组当作空桶子
- 寻访序列，并且把项目一个一个放到对应的桶子去
- 对每个不是空的桶子进行排序
- 从不是空的桶子里把项目再放回原来的序列中
用通俗易懂的话来理解：
- 将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。
算法分析
- 平均时间复杂度：
O(n + k) - 最佳时间复杂度：
O(n + k) - 最差时间复杂度：
O(n ^ 2) - 空间复杂度：
O(n * k) - 稳定性：稳定
桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大,桶排序是一种用空间换取时间的排序。
算法实现
function bucketSort(arr, num) {
if (arr.length <= 1) {
return arr
}
var len = arr.length,
buckets = [],
result = [],
min = (max = arr[0]),
regex = '/^[1-9]+[0-9]*$/',
space,
n = 0
num = num || (num > 1 && regex.test(num) ? num : 10)
for (var i = 1; i < len; i++) {
min = min <= arr[i] ? min : arr[i]
max = max >= arr[i] ? max : arr[i]
}
space = (max - min + 1) / num
for (var j = 0; j < len; j++) {
var index = Math.floor((arr[j] - min) / space)
if (buckets[index]) {
// 非空桶，插入排序
var k = buckets[index].length - 1
while (k >= 0 && buckets[index][k] > arr[j]) {
buckets[index][k + 1] = buckets[index][k]
k--
}
buckets[index][k + 1] = arr[j]
} else {
//空桶，初始化
buckets[index] = []
buckets[index].push(arr[j])
}
}
while (n < num) {
result = result.concat(buckets[n])
n++
}
return result
}