萬盛學電腦網

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

JavaScript Array.sort() 不穩定排序陷阱:多鍵排序正確姿勢

問題現場

同事代碼需對對象數組按 a 降序排序,且 b === 1 的項目優先置頂。直覺寫法:

// ❌ 錯誤示範:兩次 sort 疊加
arr.sort((a, b) => b.a - a.a);       // 第一鍵:a 降序
arr.sort((a, b) => b.b - a.b);       // 第二鍵:b 降序(期望 b=1 置頂)

結果:b=1 的項目雖然移到前面,但原本按 a 排序的相對順序被打亂,因為 JS Array.sort() 不保證穩定性(ECMAScript 2019 前規範未要求,V8 7.0 / Chrome 70+ 已實現穩定排序,但不可依賴)。

為什麼不穩定?

JS 引擎可自由選擇排序算法(V8 歷史用 QuickSort,現代用 TimSort)。不穩定排序:相等鍵值的元素相對順序可能改變。示例驗證:

var arr = Array.from({length: 20}, (_, i) => ({name: String.fromCharCode(97+i), strength: 1}));
arr.sort((a, b) => b.strength - a.strength); // 全部 strength=1,相等
console.log(arr.map(x => x.name).join(',')); // 輸出順序隨機,非 a,b,c...

正確解法:單次排序合併邏輯

// ✅ 正確:單次 sort 內部處理多鍵
arr.sort(function (a, b) {
  // 第一優先級:b=1 置頂
  if (a.b === 1 && b.b !== 1) return -1;
  if (b.b === 1 && a.b !== 1) return 1;
  // 第二優先級:a 降序
  return b.a - a.a;
});

通用多鍵排序工具函式

/**
 * 多鍵排序:支援升降序、自定義比較器
 * @param {Array} arr - 待排序數組
 * @param {Array} keys - 排序鍵配置 [{key:'a', dir:'desc'}, {key:'b', dir:'asc', cmp:fn}]
 * @returns {Array} 原數組引用(已排序)
 */
function multiSort(arr, keys) {
  return arr.sort(function (a, b) {
    for (var i = 0; i < keys.length; i++) {
      var k = keys[i];
      var va = k.key ? a[k.key] : a;
      var vb = k.key ? b[k.key] : b;
      var cmp = k.cmp || function (x, y) { return x < y ? -1 : x > y ? 1 : 0; };
      var res = cmp(va, vb);
      if (res !== 0) return k.dir === 'desc' ? -res : res;
    }
    return 0; // 完全相等保持原順序(穩定排序保證)
  });
}

// 使用
var data = [
  {name:'A', score:90, grade:1},
  {name:'B', score:85, grade:2},
  {name:'C', score:90, grade:1},
  {name:'D', score:95, grade:3}
];

multiSort(data, [
  {key: 'grade', dir: 'asc'},    // 先按 grade 升序
  {key: 'score', dir: 'desc'}    // 再按 score 降序
]);
// 結果: B(85,2), A(90,1), C(90,1), D(95,3)
// 注意:A、C 同 grade 同 score,穩定排序保證原順序 A 在 C 前

若必須多次 sort:記錄原始索引

// 方案:先掛載原始索引,最後按索引兜底
arr.forEach(function (item, i) { item._originalIndex = i; });

arr.sort((a, b) => b.a - a.a);       // 第一鍵
arr.sort((a, b) => {
  if (a.b === 1 && b.b !== 1) return -1;
  if (b.b === 1 && a.b !== 1) return 1;
  return a._originalIndex - b._originalIndex; // 兜底保持穩定
});

// 清理
arr.forEach(function (item) { delete item._originalIndex; });

現代環境:V8 7.0+ 已穩定

  • Chrome 70+ / Node 11+ / Edge 79+:Array.sort() 使用 TimSort,**穩定**
  • Safari 13+ / Firefox 65+:同樣穩定
  • 但規範未強制,跨環境(舊瀏覽器、嵌入式 JS 引擎、某些小程序容器)仍可能不穩定

結論:永遠寫單次多鍵排序,不依賴引擎實現細節,代碼更健壯、可移植。

效能補充

  • 單次 sort 為 O(n log n),多次 sort 為 k * O(n log n),單次多鍵更快
  • 大數據量(>10萬)考慮 Web Worker 離主執行緒排序,或使用 TypedArray + WASM

結語

Array.sort() 不穩定是 JS 歷史遺留特性,現代引擎雖已修正,但**編寫不依賴穩定性的代碼是專業工程師的基本素養**。單次排序合併多鍵邏輯,既正確又高效,請將此模式內化為肌肉記憶。

copyright © 萬盛學電腦網 all rights reserved