簡(jiǎn)單理解js的冒泡排序

更新時(shí)間：2016年12月19日 10:32:50 作者：循環(huán)源圈

本篇文章主要介紹了JavaScript的冒泡排序，對(duì)其進(jìn)行示例解析，具有很好的參考價(jià)值，需要的朋友一起來看下吧

關(guān)于排序，其實(shí)不管是哪種語言，都有它內(nèi)置的排序函數(shù)，我們要用的時(shí)候調(diào)用就行了，既然如此，我們?yōu)槭裁催€要講這個(gè)東西呢？我想，其實(shí)，我們講排序更多是在于排序中包含的思想算法，因?yàn)?，算法?duì)于計(jì)算機(jī)來說相當(dāng)重要，一個(gè)好的算法能夠讓計(jì)算機(jī)的效率達(dá)到事半功倍的效果，所以，算法是計(jì)算機(jī)語言中一門相當(dāng)熱門的課程，它所代表的計(jì)算機(jī)思維也是很值得我們?nèi)ド钊胙芯康摹?/p>

我也知道，關(guān)于我標(biāo)題中的排序，博客園中的很多作者都寫過詳細(xì)解釋的文章，可能，筆者本人認(rèn)為自己的理解更能體現(xiàn)出這個(gè)排序的工作原理吧，所以，筆者也就大慚不愧的在這里再次寫下關(guān)于冒泡排序的文章，有需要的讀者可以看一下。

再進(jìn)入正題之前，我給大家介紹一下谷歌瀏覽器一個(gè)很有用的調(diào)試程序代碼的功能，如果你已經(jīng)知道，請(qǐng)略過。

首先，打開谷歌瀏覽器，輸入我們的代碼腳本：

右鍵，點(diǎn)擊檢查，

按順序點(diǎn)擊，獲取腳本的運(yùn)行代碼：

我的腳本是bubble.html，存儲(chǔ)在www.test.com域名下面的js/f目錄下面，每個(gè)人的腳本不一樣，存儲(chǔ)的目錄也不一樣，請(qǐng)根據(jù)自己的情況來。

調(diào)出腳本的內(nèi)容后，下面就是調(diào)試代碼了。

選擇好了斷點(diǎn)之后，接下來在谷歌瀏覽器中再次運(yùn)行腳本，就是對(duì)下面的www.test.com/js/f/bubble.html再回車運(yùn)行

再次運(yùn)行之后，你會(huì)看到這樣的東西：

看到上面的那個(gè)藍(lán)色矩形框了嗎？這個(gè)藍(lán)色矩形框就是腳本正在運(yùn)行的代碼位置，那我們?cè)趺醋屇_本的代碼一步步的運(yùn)行呢？

這里之所以對(duì)這個(gè)腳本的for循環(huán)代碼進(jìn)行斷點(diǎn)監(jiān)控，其實(shí)，我是為了查看冒泡排序到底是怎么循環(huán)操作的，對(duì)于新手來說，這樣子直觀的查看冒泡排序代碼的運(yùn)行情況會(huì)更好的了解算法的執(zhí)行過程。

對(duì)于這個(gè)調(diào)試小功能就介紹到這里了，下面進(jìn)入正題，沒辦法直接想象出冒泡排序的執(zhí)行情況的話，你可以按我上面的步驟調(diào)出谷歌的調(diào)試功能，直觀的查看冒泡排序的整個(gè)過程。

介紹一下兩個(gè)變量互相調(diào)換的思維，我們借助中間變量來調(diào)換：

//交互元素，這里的代碼是從腳本中截取出來的，這么簡(jiǎn)單，應(yīng)該不影響理解
if(arr[j] > arr[j+1]){
mark = false;
var temp = arr[j];//temp是中間變量，把要交換的第一個(gè)元素arr[j]賦值給中間變量，也是把第一個(gè)元素存儲(chǔ)起來
arr[j] = arr[j+1];//第二個(gè)元素賦值給第一個(gè)元素，因?yàn)榈谝粋€(gè)元素我們已經(jīng)存儲(chǔ)在中間變量中了，所以我們不用擔(dān)心它的值會(huì)被覆蓋掉
arr[j+1] = temp;//temp存儲(chǔ)了第一個(gè)元素的值，把它賦值給第二個(gè)元素，就是把第一個(gè)元素賦值給第二個(gè)元素了，到這一步，兩個(gè)元素已經(jīng)交換位置了
}

再介紹一下，冒泡排序的算法過程：

冒泡排序：通過對(duì)相鄰元素的對(duì)比，并交換位置，一步一步的把一個(gè)元素給挑選出來。

舉個(gè)例子，對(duì)下面的數(shù)組進(jìn)行排序：

這是一個(gè)無序的數(shù)組：2,9,4,8,5,1,0,7,3,6

比較規(guī)則：大于>

第一輪：

第一次比較：我們把2和9作比較：2>9嗎 ?2和9比較是假，那么我們不管它，繼續(xù)向前。

第二次比較：9和4做比較，9>4嗎 ? 是真，那么我們讓它們交換值，交換了值，它們的位置不就變了嗎，是吧？怎么交換值上面已經(jīng)講過，這里不再重復(fù)了。

經(jīng)過這次交換值，原來的數(shù)組已經(jīng)變成：2,4,9,8,5,1,0,7,3,6

第三次比較：9和8做比較，9>8嗎 ? 是真，那么它們兩個(gè)繼續(xù)交換值，此時(shí)，數(shù)組已經(jīng)變成：2,4,8,9,5,1,0,7,3,6

......................

看到這里9的位置了嗎？它是不是一步一步往后移？第一次比較因?yàn)?本來就是大的，所以，它不應(yīng)該和2交換位置，因此，9沒有被放到前面去，第二次比較，因?yàn)?比4大，所以，根據(jù)比較規(guī)則，它們應(yīng)該互換位置，也就是9向后移了一位，第三次比較，依然符合比較規(guī)則，所以9和8互換位置了，9又向后移了一步，接下來的比較和上面的比較是一樣的過程，你自己比較想象一下吧，這里就不再重復(fù)了。

比較到最后一次：原數(shù)組的情況應(yīng)該是：2,4,8,5,1,0,7,3,6,9

經(jīng)過第一輪的比較，我們已經(jīng)把最大的元素給放到最后面去了，對(duì)吧？

接下來，第二輪：

首先說一下，第二輪的時(shí)候，原來的數(shù)組2,9,4,8,5,1,0,7,3,6，已經(jīng)變成了2,4,8,5,1,0,7,3,6,9，我們是在已經(jīng)冒泡過一次的數(shù)組的基礎(chǔ)上進(jìn)行比較的，先確認(rèn)這一點(diǎn)，要是你還認(rèn)為是最初的數(shù)組，那么，接下來的比較你會(huì)被搞糊涂的。呵呵。

此刻的數(shù)組：2,4,8,5,1,0,7,3,6,9

根據(jù)比較規(guī)則：2>4 嗎?是假，不管它，繼續(xù)向前比較。

4>8嗎？是假，不管它，繼續(xù)向前比較。

8>5嗎？是真，兩者交換值，也就是互換位置，此刻數(shù)組：2,4,5,8,1,0,7,3,6,9

繼續(xù)向前，8>1嗎？是真，兩者交換位置，此刻數(shù)組：2,4,5,1,8,0,7,3,6,9

.......

比較到最后，原數(shù)組又發(fā)生了改變，已經(jīng)變成：2,4,5,1,0,7,3,6,8,9

經(jīng)過兩輪的比較，原數(shù)組是否已經(jīng)變得有序一點(diǎn)了？呵呵，沒有錯(cuò)，兩輪之后，最后面的兩位數(shù)已經(jīng)是有序的了。

既然兩輪之后，最后面的兩位已經(jīng)是有序的了，那么，十輪之后呢？你自己想象一下。

十輪之后，這個(gè)數(shù)組肯定已經(jīng)排序好了。這就是冒泡排序的工作過程，相鄰元素比較，每一輪冒泡出一個(gè)有序的值。

那么，我們?cè)趺从么a的方式實(shí)現(xiàn)冒泡排序呢？

寫到這里，我想大家應(yīng)該知道怎么做了吧？

我們用兩層嵌套的for循環(huán)來實(shí)現(xiàn)這個(gè)過程，也就是實(shí)現(xiàn)冒泡排序：

//外層控制輪數(shù)
for(var i=0;i<len;i++){
　　//內(nèi)層對(duì)數(shù)組元素進(jìn)行冒泡選擇
　　for(var j=0;j<len-1-i;j++){
　　　　//交互元素
　　　　if(arr[j] > arr[j+1]){
　　　　var temp = arr[j];
　　　　arr[j] = arr[j+1];
　　　　arr[j+1] = temp;  
　　　　}
　　}
}

上面那兩個(gè)嵌套的for循環(huán)看到了嗎？外層的for循環(huán)，我們就是用來控制比較········輪數(shù)········的,

內(nèi)層的for循環(huán)，我們用來控制···················每一輪的比較次數(shù)··················的，同時(shí)，在這個(gè)for循環(huán)里面，我們還要做什么呢？上面的文字?jǐn)⑹?，你看懂了嗎？上面的文字?jǐn)⑹鲋?，我們是不是在···每一次比較···的時(shí)候，都要根據(jù)比較規(guī)則來交換數(shù)組元素的位置，是吧？那么，程序的工作過程也是一樣的，我們也要在這里根據(jù)比較規(guī)則對(duì)數(shù)組的元素進(jìn)行交換位置，為的是冒泡出我們需要的元素。

下面是冒泡排序的完整代碼，我對(duì)他進(jìn)行了優(yōu)化，當(dāng)然，如果還可以優(yōu)化，你也可以繼續(xù)優(yōu)化的。

<!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ù)字?jǐn)?shù)組
 function bubble(arr){
  //檢查參數(shù)
  if(toString.call(arr) !== '[object Array]'){
   return false;
  }
  //獲取數(shù)組長(zhǎng)度
  var len = arr.length;
  if(len <= 1){//小于1不用排序
   return arr;
  }
  //外層控制輪數(shù)
  for(var i=0;i<len;i++){
   //標(biāo)記是否有排序的元素
   var mark = true;
   //內(nèi)層對(duì)數(shù)組元素進(jìn)行冒泡選擇
   for(var j=0;j<len-1-i;j++){
    //交互元素
    if(arr[j] > arr[j+1]){
     mark = false;
     var temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp; 
    }
   }
   if(mark){
   //當(dāng)沒有進(jìn)行冒泡選擇時(shí)，證明已經(jīng)排序好了
    return arr; 
   }
  }
 }
 //測(cè)試
 var ar = [9,3,7,4,8,2,5,1,6,0];
 alert(bubble(ar));
 </script>
</head>
<body>
</body>
</html>

這里只是簡(jiǎn)單的介紹冒泡排序的工作原理，假如有時(shí)間，我再詳細(xì)講解一下另外三個(gè)排序，快速排序、選擇排序、插入排序。

其實(shí)這三個(gè)排序的工作原理都和冒泡排序很相似，網(wǎng)上也有很多文章介紹，大家可以自己研究一下。

以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時(shí)也希望多多支持腳本之家！

您可能感興趣的文章: