DIV CSS 佈局教程網

冒泡排序到底怎麼冒:從調試器到雙層循環
編輯:關於JavaScript     

幾乎每種語言都內建了排序函數,直接呼叫就好。那為什麼還要學排序?因為排序承載的是算法思想。演算法對電腦的重要性不言自明,好演算法能讓效率事半功倍,而它所代表的計算思維,值得花時間細細體會。

關於冒泡排序,前輩們已經寫過很多精闢的文章。我這裡換個角度,試著把它的執行過程講得更具體一些。

先用調試器把過程「看」出來

如果光靠想像無法建立畫面,建議直接讓瀏覽器把每一輪的變化演出來。

打開 Chrome,載入你的腳本頁面:

右鍵選擇「檢查」:

依序切換到 Sources,找到你的腳本:

我的腳本是 bubble.html,放在 www.test.com 的 js/f/ 目錄下。你的檔名與路徑應該不同,按自己的情況找即可。

在 for 循環那幾行打上斷點——這正是我想觀察冒泡每一輪怎麼運作的位置。

回到瀏覽器重新執行腳本:

那個藍色矩形標出了當前暫停的執行位置。接下來用單步執行按鈕,就能一行一行往下走:

對新手而言,這樣直觀地看著變量變化,比讀十遍文字都有用。

兩個變量怎麼交換

借助中間變量,這是最直白的做法:

 // 交互元素
 if(arr[j] > arr[j+1]){
   mark = false;
   var temp = arr[j];   // 把第一個元素存入中間變量
   arr[j] = arr[j+1];   // 第二個元素給第一個,此時原值已安全存在 temp 中
   arr[j+1] = temp;     // temp 的值給第二個元素,交換完成
 }

算法過程:一輪冒出一個

冒泡排序本質是:比較相鄰兩元素,若順序不對就交換,一趟走完整個元素就被挑選出來。

拿這組無序數組說明:2,9,4,8,5,1,0,7,3,6,比較規則為「大於」。

第一輪:

  • 2 與 9 比較,2 > 9 為假,不動,繼續。
  • 9 與 4 比較,為真,交換 → 2,4,9,8,5,1,0,7,3,6
  • 9 與 8 比較,為真,交換 → 2,4,8,9,5,1,0,7,3,6
  • …… 以此類推

注意 9 的軌跡:因為它本來就比 2 大,所以沒被換到前面;接著每遇到一個更小的數就後退一格,像氣泡一樣一路浮到最右端。第一輪結束時數組變成 2,4,8,5,1,0,7,3,6,9,最大值已經到位。

第二輪:出發點是上一輪的結果,這一點要特別確認,否則會看糊塗。

  • 2 > 4 假,不動
  • 4 > 8 假,不動
  • 8 > 5 真,交換 → 2,4,5,8,1,0,7,3,6,9
  • 8 > 1 真,交換 → 2,4,5,1,8,0,7,3,6,9
  • …… 直到 2,4,5,1,0,7,3,6,8,9

兩輪之後,末尾兩位已經有序。以此類推,十輪之後整個數組必然排好——元素有幾個,最多就需要幾輪。

用雙層循環落地

 // 外層控制輪數
 for(var i=0;i<len;i++){
   // 內層對數組元素進行冒泡選擇
   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;
     }
   }
 }

分工很清楚:外層管第幾輪,內層管每一輪比幾次,並在每次比較時依規則交換位置。內層的 len-1-i 是個關鍵優化——末尾 i 個元素已經就位,不必再比。

完整代碼(含提前退出優化)

 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="https://www.w3.org/1999/xhtml" xml:lang="zh-cn">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
<title>冒泡排序</title>
<script type="text/javascript">
 // 參數:數字數組
 function bubble(arr){
   // 檢查參數
   if(toString.call(arr) !== '[object Array]'){
     return false;
   }
   var len = arr.length;
   if(len <= 1){          // 小於等於 1 個元素無需排序
     return arr;
   }
   // 外層控制輪數
   for(var i=0;i<len;i++){
     var mark = true;     // 標記本輪是否發生過交換
     // 內層進行冒泡選擇
     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){
       // 本輪一次交換都沒發生,說明已經有序,提前收工
       return arr;
     }
   }
   return arr;
 }

 // 測試
 var ar = [9,3,7,4,8,2,5,1,6,0];
 alert(bubble(ar));
</script>
</head>
<body>
</body>
</html>

那個 mark 標記是實務上很重要的一手:若某輪完全沒有交換,代表序列已有序,可直接跳出,對近乎排序好的資料能省下大量比較。

本文只講冒泡。快速排序、選擇排序、插入排序的原理與它有相通之處,網上也有不少好文章,有興趣可以自己往下鑽。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved