JS桶排序的簡單理解與實現(xiàn)方法示例

更新時間：2019年11月25日 10:26:24 作者：循環(huán)源圈

這篇文章主要介紹了JS桶排序的簡單理解與實現(xiàn)方法,結(jié)合實例形式詳細分析了js桶排序的概念、原理、實現(xiàn)方法及操作注意事項,需要的朋友可以參考下

本文實例講述了JS桶排序的簡單理解與實現(xià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ù)字進行分桶。首先，最大數(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ù)值范圍來分桶的，所以理所當(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程序的實現(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ù)組模擬桶
        //獲取桶最后一個值的下標(biāo) 
        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>

感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

您可能感興趣的文章: