溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

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

發(fā)布時間：2021-06-04 15:07:29 來源：億速云 閱讀：153 作者：小新 欄目：web開發(fā)

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

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

利用上面的例子做解釋：

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

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

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

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

我們讓每個數(shù)字減去最小值再除以一個桶的取值范圍就可以獲得這個數(shù)字所對應(yīng)的桶編號了，為什么這么說呢？因為我們就是利用數(shù)值范圍來分桶的，所以理所當然的也是獲取每個數(shù)字的取值范圍來分桶的編號，而最小值就是我們的取值標準，當然是要每個數(shù)字都減去它才能準確的獲取每個數(shù)的取值范圍了。

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

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

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

下面是js程序的實現(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];
    //默認桶的個數(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);
      //桶里是否有值，有值則進行排序
      if(list[index]){//用數(shù)組模擬桶
        //獲取桶最后一個值的下標 
        var k=list[index].length - 1;
        //桶最后的值大于要插進來的值，所以要把這個值插到桶的前面去，但不知道這個值要插入到前面的哪個位置，所以，就只能對比排序了
          //對桶進行排序
          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如何實現(xiàn)桶排”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

js
AI
助
手