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

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

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

本文實(shí)例講述了JS桶排序的簡(jiǎn)單理解與實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：

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

舉個(gè)易于理解的例子：

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

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

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

利用上面的例子做解釋：

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

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

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

知道了這些之后，我們?cè)趺粗烂總€(gè)數(shù)字所對(duì)應(yīng)的桶的編號(hào)呢？

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

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

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

其他的數(shù)字獲取桶編號(hào)都是同樣的原理，這里就不再重復(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)頁(yè)描述" />
  <link rel="stylesheet" type="text/css" href="" />
  <style type="text/css"></style>
  <script type="text/javascript">
  //桶排序,參數(shù)數(shù)組,桶的個(gè)數(shù)，這里用數(shù)組模擬桶
  var cask=function (arr,caskCount){
    //不是數(shù)組，返回false
    if(toString.call(arr) != '[object Array]'){
      return false;
    }
    //獲取數(shù)組的長(zhǎng)度
    var len = arr.length;
    if(len <=1){
      return arr;//長(zhǎng)度小于等于1不用排序
    }
    var list  = [],//裝桶的桶，用它來控制存儲(chǔ)桶的編號(hào)
      result = [],//返回的結(jié)果
      max  = arr[0],
      min  = arr[0];
    //默認(rèn)桶的個(gè)數(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個(gè)桶，桶所占用的范圍
    var range = (max - min) / caskCount;
    for(var i=0;i<len;i++){
      //桶的數(shù)值減去最小數(shù) min 獲取的是桶占用的范圍，再除以一個(gè)桶的范圍，就是獲取對(duì)應(yīng)的桶編號(hào)
      var index = Math.floor((arr[i] - min) / range);
      //桶里是否有值，有值則進(jìn)行排序
      if(list[index]){//用數(shù)組模擬桶
        //獲取桶最后一個(gè)值的下標(biāo) 
        var k=list[index].length - 1;
        //桶最后的值大于要插進(jìn)來的值，所以要把這個(gè)值插到桶的前面去，但不知道這個(gè)值要插入到前面的哪個(gè)位置，所以，就只能對(duì)比排序了
          //對(duì)桶進(jìn)行排序
          while(k >=0 && list[index][k] > arr[i]){
            //桶前面的數(shù)字放到后面去
            list[index][k+1] = list[index][k];//第一個(gè)k+1為新增的桶
            //小的提前一個(gè)位置
            //list[index][k] = arr[i];
            k--;
          }
        //不用排序的，直接加在桶的最后面
        list[index][k+1] = arr[i];
      }else{
      //沒有值則生成桶，并把值放到對(duì)應(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代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun測(cè)試上述代碼運(yùn)行效果。

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

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

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

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

您可能感興趣的文章: