介绍
桶排序是最简单的排序算法，举例说明：有场景下有数据范围是0~n，我们假设已经有n+1个桶用于排序，将需要被排序的数据一个个放入对应的桶的序号中，即数据 3被放入第3个桶，数据67被放入第67个桶，一个桶可装多个数；最终从头到尾（升序）或者从尾到头（降序）找出桶里的数据。
例子
假设有一个待排序数组[77, 6, 37, 96, 34, 6,14], 桶排序的js实现如下(升序)：
function sort(arr){
var buckets = [], //辅助桶
result = []; //用于保存结果
//待排序数据依次放入桶，这里遍历n次
arr.forEach(function(item){
//一个桶可以装多个数，所以用数组装
if(buckets[item]) buckets[item].push(item);
else buckets[item] = [item];
});
//将桶里从头到尾连起来输出,这里遍历n次
buckets.forEach(function(item){
if(item) result = result.concat(item);
})
return result;
}
var arr = [77, 6, 37, 96, 34, 6, 14];
console.log(sort(arr)); // =>[6, 6, 14, 34, 37, 77, 96]
时间复杂度
大O阶计算f(n) = n + n = 2n，所以时间复杂度为O(n)。虽然时间上消耗还算ok，但桶排序有个致命的缺点：浪费空间。
感谢阅读！欢迎关注！持续更新中...
