冒泡排序是最容易寫 also 最容易理解 的排序演算法:反覆比較相鄰元素,把較大的往後推,每一輪都能把當前最大值「浮」到末端,因此得名。本文在基本版本之外,再實現雙向冒泡(雞尾酒排序)與一個變體,並說明它們的改善思路。
這裡用「交換」而非建立暫存陣列的方式進行,透過加減法避免額外變數(實務上建議直接用暫存變數,可讀性更好也更不易溢位):
var ls = [98, 13, 6, 25, 38, 36, 30, 44, 38, 80, 61, 28, 47, 34, 95, 18, 85, 58,
89, 85, 42, 61, 74, 35, 13, 14, 80, 7, 10, 44, 10, 47, 13, 11, 52, 25,
24, 48, 34, 12, 88, 80, 33, 8, 80, 45, 64, 52, 79, 77];
for (var i = 0; i < ls.length; i++) {
for (var j = i + 1; j < ls.length; j++) {
if (ls[i] > ls[j]) {
ls[i] = ls[i] + ls[j];
ls[j] = ls[i] - ls[j];
ls[i] = ls[i] - ls[j];
}
}
}
這個寫法讓每一輪確定第 i 個位置的最小值,本質上與選擇排序更接近;若要體現經典冒泡的「相鄰比較」,內層應寫成 for (var j = 0; j < ls.length - 1 - i; j++) 並比較 ls[j] 與 ls[j+1]。
基本冒泡每一輪只能固定一個元素,若最小的元素恰好在末尾,它需要走完整趟才能到位,效率很差。雙向冒泡(又稱雞尾酒排序)的改進是:一輪之內先由左向右把最大值推到右端,再由右向左把最小值推回左端,兩端同時收斂。
var ls = [6, 13, 98, 25, 38, 36, 30, 44, 38, 80, 61, 28, 47, 34, 95, 18, 85, 58,
89, 85, 42, 61, 74, 35, 13, 14, 80, 7, 10, 44, 10, 47, 13, 11, 52, 25,
24, 48, 34, 12, 88, 80, 33, 8, 80, 45, 64, 52, 79, 77];
var lent = ls.length;
for (var i = 0; i < ls.length; i++) {
for (var j = i + 1; j < ls.length - i; j++) {
// 由右向左:把較小的往左推
if (ls[lent - 1 - i] < ls[lent - j]) {
ls[lent - 1 - i] = ls[lent - 1 - i] + ls[lent - j];
ls[lent - j] = ls[lent - 1 - i] - ls[lent - j];
ls[lent - 1 - i] = ls[lent - 1 - i] - ls[lent - j];
}
// 由左向右:把較大的往右推
if (ls[i] > ls[j]) {
ls[i] = ls[i] + ls[j];
ls[j] = ls[i] - ls[j];
ls[i] = ls[i] - ls[j];
}
}
}
注意上述程式碼中的 lent 是刻意保留的變數名,實際使用時建議改為更具描述性的 len。核心改進在於內層迴圈的邊界 ls.length - i:每完成一輪,右側已就位的元素就不再參與比較。
以下版本嘗試在每一輪中同時處理「當前最小值」「當前最大值」「倒數第二小」「順數第二大」四個位置,以減少迴圈趟數:
var ls = [98, 13, 6, 25, 38, 36, 30, 44, 38, 80, 61, 28, 47, 34, 95, 18, 85, 58,
89, 85, 42, 61, 74, 35, 13, 14, 80, 7, 10, 44, 10, 47, 13, 11, 52, 25,
24, 48, 34, 12, 88, 80, 33, 8, 80, 45, 64, 52, 79, 77];
var lent = ls.length;
for (var i = 0; i < ls.length; i++) {
for (var j = i * 2; j < ls.length - 2 * i; j++) {
// 保持內層第一個數為本輪最小
if (ls[i * 2] > ls[j + 1]) {
ls[i * 2] = ls[i * 2] + ls[j + 1];
ls[j + 1] = ls[i * 2] - ls[j + 1];
ls[i * 2] = ls[i * 2] - ls[j + 1];
}
// 保持內層倒數第一個數為本輪最大
if (ls[lent - i * 2 - 1] < ls[lent - j - 1]) {
ls[lent - i * 2 - 1] = ls[lent - i * 2 - 1] + ls[lent - j - 1];
ls[lent - j - 1] = ls[lent - i * 2 - 1] - ls[lent - j - 1];
ls[lent - i * 2 - 1] = ls[lent - i * 2 - 1] - ls[lent - j - 1];
}
// 倒數第二個位置
if (ls[lent - 2 - i * 2] < ls[lent - j - 1]) {
ls[lent - 2 - i * 2] = ls[lent - 2 - i * 2] + ls[lent - j - 1];
ls[lent - j - 1] = ls[lent - 2 - i * 2] - ls[lent - j - 1];
ls[lent - 2 - i * 2] = ls[lent - 2 - i * 2] - ls[lent - j - 1];
}
// 順數第二個位置
if (ls[i * 2 + 1] > ls[j + 1]) {
ls[i * 2 + 1] = ls[i * 2 + 1] + ls[j + 1];
ls[j + 1] = ls[i * 2 + 1] - ls[j + 1];
ls[i * 2 + 1] = ls[i * 2 + 1] - ls[j + 1];
}
}
}
冒泡排序的平均與最壞時間複雜度都是 O(n²),空間複雜度 O(1),且是穩定排序。雙向冒泡在「最小元素位於尾端」這類特定分布上能少走一半路程,實測通常比單向版本快,但數量級並未改變。
上面三段程式碼刻意示範了以加減法交換、以及多重索引運算的寫法,這是為了貼近原始思路;在實際專案中更推薦:
left/right 兩個邊界變數,並在每輪結束時向內收縮,程式碼會比 lent - i * 2 - 1 這類表達式清楚得多。需要處理大量資料時,請直接改用快速排序、合併排序或堆排序等 O(n log n) 的演算法;冒泡排序的價值主要在教學與極小規模資料。