冒泡排序是教學經典,實際項目中極少直接使用(O(n²))。本文提供標準冒泡、優化冒泡(提前終止)、雙向冒泡(雞尾酒排序),並對比原生 Array.prototype.sort 的高性能實現與自定義比較函數用法。
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) { // 趟數
for (var j = 0; j < len - 1 - i; j++) { // 每趟比較次數遞減
if (arr[j] > arr[j + 1]) {
var tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr; // 原地排序,也返回引用
}
function bubbleSortOptimized(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
var swapped = false;
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
var tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) break; // 本趟無交換,已有序
}
return arr;
}
function cocktailSort(arr) {
var left = 0, right = arr.length - 1;
while (left < right) {
var swapped = false;
// 正向:將大元素冒泡到右端
for (var i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); swapped = true; }
}
right--;
// 反向:將小元素沉底到左端
for (var i = right; i > left; i--) {
if (arr[i] < arr[i - 1]) { swap(arr, i, i - 1); swapped = true; }
}
left++;
if (!swapped) break;
}
return arr;
}
function swap(arr, i, j) { var t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
// 數字升序(必須提供比較函數,否則按字符串 Unicode 排序)
var nums = [2, 4, 8, 1, 22, 3];
nums.sort((a, b) => a - b); // [1, 2, 3, 4, 8, 22]
// 降序
nums.sort((a, b) => b - a);
// 對象數組按字段排序
var users = [{age: 25}, {age: 18}, {age: 30}];
users.sort((a, b) => a.age - b.age);
// 多字段排序:先按 age 升序,age 同則 name 降序
users.sort((a, b) => a.age - b.age || b.name.localeCompare(a.name));
| 陷阱 | 現象 | 修正 |
|---|---|---|
直接 arr.sort() | [1, 2, 22, 3, 4, 8] (字符串序) | 必須傳 (a,b)=>a-b |
| 修改原數組 | sort 就地排序,返回同一引用 | 需保留原數組用 arr.slice().sort(...) |
| 比較函數返回非數字 | 行為未定義 | 嚴格返回 < 0, 0, > 0 |
| 稳定性 | ES2019 規定穩定排序 | 現代瀏覽器均穩定,可放心多鍵排序 |
| 算法 | 平均/最壞 | 空間 | 穩定 | JS 內部實現 |
|---|---|---|---|---|
| 冒泡 | O(n²) | O(1) | 是 | 教學用 |
| 優化冒泡 | O(n²) / O(n) 最好 | O(1) | 是 | — |
| 雞尾酒 | O(n²) | O(1) | 是 | — |
| V8 Timsort (sort) | O(n log n) | O(n) | 是 | 混合插入+歸併,高度優化 |
arr.sort(compareFn),不可手寫 O(n²) 排序。冒泡排序僅作教學參考,生產代碼請直接使用原生 sort。