每天一点算法-桶排序 (Day2)

介绍

桶排序是最简单的排序算法，举例说明：有场景下有数据范围是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，但桶排序有个致命的缺点：浪费空间。

感谢阅读！欢迎关注！持续更新中...