JS如何实现桶排

这篇文章给大家分享的是有关JS如何实现桶排的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

为大邑县等地区用户提供了全套网页设计制作服务，及大邑县网站建设行业解决方案。主营业务为成都网站建设、网站设计、大邑县网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

桶排序，利用编号分组存储数字，再利用编号合并分组的一种算法排序。

举个易于理解的例子：

一组数字，9,3,4,0,2,8,5,1,7,6,11,10,18,15,17,12,16,13,19,14

我们把这组数字分组编号成10个桶装起来，但怎么编号分组呢？

这里我们利用数字范围来对数字进行分桶。首先，最大数减去最小数，获取这组数字的取值范围，然后，我们让这个取值范围除以桶数，获取一个桶的取值范围，既然知道一个桶的取值范围，那么，通过对比每个数字占用多少个桶，我们就可以获取这个数字所对应的桶的编号了。（换一句话说，就是每个数字占用多少个取值范围，这里的桶其实就是数字的取值范围的具体化东西）

利用上面的例子做解释：

上面的最大值是19，最小值是0，所以这组数的取值范围是：19-0=19。

我们要用10个桶来分装这组数字，则一个桶的取值范围是：19 / 10 = 1.9。

所以，一个桶的取值范围就是：1.9。

知道了这些之后，我们怎么知道每个数字所对应的桶的编号呢？

我们让每个数字减去最小值再除以一个桶的取值范围就可以获得这个数字所对应的桶编号了，为什么这么说呢？因为我们就是利用数值范围来分桶的，所以理所当然的也是获取每个数字的取值范围来分桶的编号，而最小值就是我们的取值标准，当然是要每个数字都减去它才能准确的获取每个数的取值范围了。

根据上面的解释，那么，第一个数字的桶编号就是：(9-0) / 1.9 = 4.7368·······

当然为了确保编号为整数，我们必须给编号取整，这里我们是向上取整，所以第一个数：9的桶编号就是5啦。

其他的数字获取桶编号都是同样的原理，这里就不再重复叙述了。

下面是js程序的实现：

  
  
  
  
  
  
  
  //桶排序,参数数组,桶的个数，这里用数组模拟桶
  var cask=function (arr,caskCount){
    //不是数组，返回false
    if(toString.call(arr) != '[object Array]'){
      return false;
    }
    //获取数组的长度
    var len = arr.length;
    if(len <=1){
      return arr;//长度小于等于1不用排序
    }
    var list  = [],//装桶的桶，用它来控制存储桶的编号
      result = [],//返回的结果
      max  = arr[0],
      min  = arr[0];
    //默认桶的个数为10
    var  caskCount = parseInt(caskCount) > 0 ? parseInt(caskCount) : 10;
    //获取数组的最大值和最小值
    for(var i=1;i= min ? min : arr[i] ; 
    }
    //分成caskCount个桶，桶所占用的范围
    var range = (max - min) / caskCount;
    for(var i=0;i=0 && list[index][k] > arr[i]){
            //桶前面的数字放到后面去
            list[index][k+1] = list[index][k];//第一个k+1为新增的桶
            //小的提前一个位置
            //list[index][k] = arr[i];
            k--;
          }
        //不用排序的，直接加在桶的最后面
        list[index][k+1] = arr[i];
      }else{
      //没有值则生成桶，并把值放到对应的桶中
        list[index]=[];
        list[index][0]=arr[i];
      }
    }
    //合并桶
    var n=0;
    while(n <= caskCount){
      if(list[n]){
        result = result.concat(list[n]);
      }
      n++;
    }
    return result;
  }
  var arr=[8,39,400,500,3,4,20,44,440];
  alert(cask(arr,10));
  //alert(parseInt(-1) ? parseInt(-1) : 1);
  

感谢各位的阅读！关于“JS如何实现桶排”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！

本文标题：JS如何实现桶排
转载注明：http://shouzuofang.com/article/iegshp.html