氣泡排序是最直覺的排序演算法,它的比對規則只有一句話:相鄰兩個元素,如果左邊比右邊大,就交換它們。
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 次。
氣泡排序的價值主要在教學:它把「比較—交換—收斂」這套排序思維講得最清楚。實務上請直接用 Array.prototype.sort。