冒泡排序的目標是把陣列元素依序排好。名稱來自於每一輪比較時,較大的元素會像氣泡一樣往尾端浮。
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() 已在引擎層最佳化,數值排序時記得傳入比較函式即可。