DIV CSS 佈局教程網

JavaScript 冒泡排序實作與三種優化寫法
編輯:JavaScript基礎知識     

冒泡排序的目標是把陣列元素依序排好。名稱來自於每一輪比較時,較大的元素會像氣泡一樣往尾端浮。

var array = [9, 8, 7, 6, 5, 4, 3, 2, 1];

逐輪追蹤

第一輪:8,7,6,5,4,3,2,1,9  交換 8 次  i=0,j 走到 array.length-1-i

第二輪:7,6,5,4,3,2,1,8,9  交換 7 次  i=1

第三輪:6,5,4,3,2,1,7,8,9  交換 6 次  i=2

第四輪:5,4,3,2,1,6,7,8,9  交換 5 次  i=3

第五輪:4,3,2,1,5,6,7,8,9  交換 4 次  i=4

第六輪:3,2,1,4,5,6,7,8,9  交換 3 次  i=5

第七輪:2,1,3,4,5,6,7,8,9  交換 2 次  i=6

第八輪:1,2,3,4,5,6,7,8,9  交換 1 次  i=7

規律很清楚:外層控制輪數,內層控制每輪的比較次數,而每完成一輪,尾端就多一個已排定的元素,所以內層上界要減掉 i。

基本實作

var temp;
var array = [9, 8, 7, 6, 5, 4, 3, 2, 1];

// 外層循環控制輪數
for (var i = 0; i < array.length - 1; i++) {
  // 內層循環控制比較次數
  for (var j = 0; j < array.length - 1 - i; j++) {
    if (array[j] > array[j + 1]) {
      temp = array[j];
      array[j] = array[j + 1];
      array[j + 1] = temp;
    }
  }
}
console.log(array);

優化一:加入交換旗標提前結束

若某一輪完全沒有發生交換,代表資料已經有序,可以直接跳出。

var temp, bool, m = 0;
var array = [9, 8, 7, 6, 5, 4, 3, 2, 1];

for (var i = 0; i < array.length - 1; i++) {
  bool = true; // 開關預設為開
  for (var j = 0; j < array.length - 1 - i; j++) {
    if (array[j] > array[j + 1]) {
      temp = array[j];
      array[j] = array[j + 1];
      array[j + 1] = temp;
      bool = false; // 有交換就關掉開關
    }
  }
  if (bool) { break; } // 這一輪沒交換,提前收工
  m++;
}
console.log(array + ",比較 " + m + " 輪");

備註:最好情況是 0 輪(原本就有序,第一輪結束即退出),最壞是 8 輪。

優化二:掛到原型上

以下寫法出自《JavaScript 語言精粹》的 method 輔助函式,示範如何替基礎型別擴充方法。由於 Array 與 String 本身也是建構函式,Array.prototype 最終指向 Function.prototype,因此 Array.method 呼叫時,會先在 Array 自身找不到 method,接著在 Array.prototype 仍找不到,最後在 Function.prototype 命中。

Function.prototype.method = function (name, func) {
  if (!this.prototype[name]) {
    this.prototype[name] = func;
  }
  return this;
};

Array.method('bubble', function () {
  var len = this.length;
  var i = 0, j = 0, tmp = 0;
  for (i = 0; i < len; i++) {
    for (j = 0; (j + 1) < len - i; j++) {
      if (this[j] > this[j + 1]) {
        tmp = this[j];
        this[j] = this[j + 1];
        this[j + 1] = tmp;
      }
    }
  }
  return this;
});

alert([21, 32, 1, 31, 22, 45, 68, 37].bubble());

要提醒的是,直接擴充內建物件原型容易造成命名衝突,在多人協作或使用第三方函式庫的專案中風險不小,僅建議當作理解原型的練習。

優化三:從尾端往前冒

另一種常見寫法(西風瘦馬)把內層改成從後往前比較,並同樣用交換旗標提前終止。

var list = Array(23, 45, 18, 37, 92, 13, 24);
var n = list.length;
var tmp;
var exchange;

// 最多做 n-1 趟
for (var time = 0; time < n - 1; time++) {
  exchange = false;
  for (var i = n - 1; i > time; i--) {
    if (list[i] < list[i - 1]) {
      exchange = true;
      tmp = list[i - 1];
      list[i - 1] = list[i];
      list[i] = tmp;
    }
  }
  if (!exchange) { break; } // 本趟未交換,提前結束
}
alert('數組排序後為:' + list + ',共排了 ' + time + ' 趟');

另一份寫法

function BubbleSort(array) {
  var length = array.length;
  var temp;
  var isSort = false;
  for (var i = 1; i < length; i++) {
    isSort = false;
    for (var j = 0; j < length - i; j++) {
      if (array[j] > array[j + 1]) {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
        isSort = true;
      }
    }
    if (!isSort) { break; }
  }
}

var array = [10, -3, 5, 34, -34, 5, 0, 9];
BubbleSort(array);
for (var i = 0; i < array.length; i++) {
  document.write(array[i] + " ");
}

關於效能

冒泡排序的時間複雜度為 O(n²),加上旗標優化後最好情況可降到 O(n),但平均與最壞仍是 O(n²)。它最大的價值在教學——清楚展示雙層迴圈、交換與提前終止的概念。真正要處理大量資料時,原生 Array.prototype.sort() 已在引擎層最佳化,數值排序時記得傳入比較函式即可。

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