JS如何實(shí)現(xiàn)桶排

這篇文章給大家分享的是有關(guān)JS如何實(shí)現(xiàn)桶排的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

為大邑縣等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及大邑縣網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計、大邑縣網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

桶排序，利用編號分組存儲數(shù)字，再利用編號合并分組的一種算法排序。

舉個易于理解的例子：

一組數(shù)字，9,3,4,0,2,8,5,1,7,6,11,10,18,15,17,12,16,13,19,14

我們把這組數(shù)字分組編號成10個桶裝起來，但怎么編號分組呢？

這里我們利用數(shù)字范圍來對數(shù)字進(jìn)行分桶。首先，最大數(shù)減去最小數(shù)，獲取這組數(shù)字的取值范圍，然后，我們讓這個取值范圍除以桶數(shù)，獲取一個桶的取值范圍，既然知道一個桶的取值范圍，那么，通過對比每個數(shù)字占用多少個桶，我們就可以獲取這個數(shù)字所對應(yīng)的桶的編號了。（換一句話說，就是每個數(shù)字占用多少個取值范圍，這里的桶其實(shí)就是數(shù)字的取值范圍的具體化東西）

利用上面的例子做解釋：

上面的最大值是19，最小值是0，所以這組數(shù)的取值范圍是：19-0=19。

我們要用10個桶來分裝這組數(shù)字，則一個桶的取值范圍是：19 / 10 = 1.9。

所以，一個桶的取值范圍就是：1.9。

知道了這些之后，我們怎么知道每個數(shù)字所對應(yīng)的桶的編號呢？

我們讓每個數(shù)字減去最小值再除以一個桶的取值范圍就可以獲得這個數(shù)字所對應(yīng)的桶編號了，為什么這么說呢？因?yàn)槲覀兙褪抢脭?shù)值范圍來分桶的，所以理所當(dāng)然的也是獲取每個數(shù)字的取值范圍來分桶的編號，而最小值就是我們的取值標(biāo)準(zhǔn)，當(dāng)然是要每個數(shù)字都減去它才能準(zhǔn)確的獲取每個數(shù)的取值范圍了。

根據(jù)上面的解釋，那么，第一個數(shù)字的桶編號就是：(9-0) / 1.9 = 4.7368·······

當(dāng)然為了確保編號為整數(shù)，我們必須給編號取整，這里我們是向上取整，所以第一個數(shù)：9的桶編號就是5啦。

其他的數(shù)字獲取桶編號都是同樣的原理，這里就不再重復(fù)敘述了。

下面是js程序的實(shí)現(xiàn)：

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh-cn">
<head>
  <meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
  <title>桶排序</title>
  <meta name="keywords" content="關(guān)鍵字列表" />
  <meta name="description" content="網(wǎng)頁描述" />
  <link rel="stylesheet" type="text/css" href="" />
  <style type="text/css"></style>
  <script type="text/javascript">
  //桶排序,參數(shù)數(shù)組,桶的個數(shù)，這里用數(shù)組模擬桶
  var cask=function (arr,caskCount){
    //不是數(shù)組，返回false
    if(toString.call(arr) != '[object Array]'){
      return false;
    }
    //獲取數(shù)組的長度
    var len = arr.length;
    if(len <=1){
      return arr;//長度小于等于1不用排序
    }
    var list  = [],//裝桶的桶，用它來控制存儲桶的編號
      result = [],//返回的結(jié)果
      max  = arr[0],
      min  = arr[0];
    //默認(rèn)桶的個數(shù)為10
    var  caskCount = parseInt(caskCount) > 0 ? parseInt(caskCount) : 10;
    //獲取數(shù)組的最大值和最小值
    for(var i=1;i<len-1;i++){
       max = arr[i] <= max ? max : arr[i] ; 
       min = arr[i] >= min ? min : arr[i] ; 
    }
    //分成caskCount個桶，桶所占用的范圍
    var range = (max - min) / caskCount;
    for(var i=0;i<len;i++){
      //桶的數(shù)值減去最小數(shù) min 獲取的是桶占用的范圍，再除以一個桶的范圍，就是獲取對應(yīng)的桶編號
      var index = Math.floor((arr[i] - min) / range);
      //桶里是否有值，有值則進(jìn)行排序
      if(list[index]){//用數(shù)組模擬桶
        //獲取桶最后一個值的下標(biāo) 
        var k=list[index].length - 1;
        //桶最后的值大于要插進(jìn)來的值，所以要把這個值插到桶的前面去，但不知道這個值要插入到前面的哪個位置，所以，就只能對比排序了
          //對桶進(jìn)行排序
          while(k >=0 && list[index][k] > arr[i]){
            //桶前面的數(shù)字放到后面去
            list[index][k+1] = list[index][k];//第一個k+1為新增的桶
            //小的提前一個位置
            //list[index][k] = arr[i];
            k--;
          }
        //不用排序的，直接加在桶的最后面
        list[index][k+1] = arr[i];
      }else{
      //沒有值則生成桶，并把值放到對應(yīng)的桶中
        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);
  </script>
</head>
<body>
</body>
</html>

感謝各位的閱讀！關(guān)于“JS如何實(shí)現(xiàn)桶排”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！

文章標(biāo)題：JS如何實(shí)現(xiàn)桶排
新聞來源：http://muchs.cn/article48/iegshp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、網(wǎng)站設(shè)計公司、品牌網(wǎng)站建設(shè)、網(wǎng)站收錄、小程序開發(fā)、標(biāo)簽優(yōu)化

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容