DIV CSS 佈局教程網

JavaScript 氣泡排序(Bubble Sort)原理與實作全解
編輯:JavaScript基礎知識     

氣泡排序是最直覺的排序演算法,它的比對規則只有一句話:相鄰兩個元素,如果左邊比右邊大,就交換它們。

排序流程

  1. 從頭開始掃過每一對相鄰元素,掃到尾端時,最大的元素必然被「推」到了最後一格。
  2. 第二輪不必再碰最後一格,只需掃到倒數第二格。
  3. 每一輪都比上一輪少比對一格,直到某一輪完全沒有發生任何交換,代表序列已排序完成,可以提早結束。

程式碼實作

function sort(elements) {
  for (var i = 0; i < elements.length - 1; i++) {
    var swapped = false;                       // 本輪是否發生過交換
    // 每跑完一輪,尾端 i 個元素已就位,內層不必再比對
    for (var j = 0; j < elements.length - i - 1; j++) {
      if (elements[j] > elements[j + 1]) {
        var tmp = elements[j];
        elements[j] = elements[j + 1];
        elements[j + 1] = tmp;
        swapped = true;
      }
    }
    if (!swapped) break;                       // 一輪都沒換,直接收工
  }
  return elements;
}

var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements);
console.log('after : ' + elements);

那個 swapped 旗標不是裝飾。原本需要固定跑 n-1 輪的版本,遇到已排序或接近排序的資料時會做出一堆無意義的比較;加上提前中止後,這種情境的比較次數直接降到 n-1 次。

效率分析

  • 時間複雜度:最佳 O(n)(序列本來就有序,靠旗標一輪結束)、平均與最差 O(n²)。
  • 空間複雜度:O(1),只用了一個暫存變數,屬於原地排序。
  • 穩定性:穩定。只有在嚴格大於時才交換,相同值不會被調換位置。

氣泡排序的價值主要在教學:它把「比較—交換—收斂」這套排序思維講得最清楚。實務上請直接用 Array.prototype.sort。

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