萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 數組冒泡排序完整實現與優化、ES6 sort 替代方案

冒泡排序是教學經典,實際項目中極少直接使用(O(n²))。本文提供標準冒泡、優化冒泡(提前終止)、雙向冒泡(雞尾酒排序),並對比原生 Array.prototype.sort 的高性能實現與自定義比較函數用法。

1. 標準冒泡排序(原文示例)

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; // 原地排序,也返回引用
}

2. 優化一:提前終止標記

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;
}

3. 優化二:雞尾酒排序(雙向冒泡,減少「海龜」元素移動)

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; }

4. 生產環境首選:Array.prototype.sort

// 數字升序(必須提供比較函數,否則按字符串 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));

5. sort 陷阱與避坑

陷阱現象修正
直接 arr.sort()[1, 2, 22, 3, 4, 8] (字符串序)必須傳 (a,b)=>a-b
修改原數組sort 就地排序,返回同一引用需保留原數組用 arr.slice().sort(...)
比較函數返回非數字行為未定義嚴格返回 < 0, 0, > 0
稳定性ES2019 規定穩定排序現代瀏覽器均穩定,可放心多鍵排序

6. 複雜度對比

算法平均/最壞空間穩定JS 內部實現
冒泡O(n²)O(1)是教學用
優化冒泡O(n²) / O(n) 最好O(1)是—
雞尾酒O(n²)O(1)是—
V8 Timsort (sort)O(n log n)O(n)是混合插入+歸併,高度優化

7. 實戰建議

  1. 業務代碼永遠用 arr.sort(compareFn),不可手寫 O(n²) 排序。
  2. 學習算法原理時,實現冒泡/快排/歸併理解分治思想。
  3. 比較函數盡量純函數、無副作用、避免訪問外部狀態。
  4. 大數據排序考慮 Web Worker 分片或 IndexedDB 索引。

冒泡排序僅作教學參考,生產代碼請直接使用原生 sort。

copyright © 萬盛學電腦網 all rights reserved