大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

每天一点算法-桶排序 (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,但桶排序有个致命的缺点:浪费空间。

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