排序看似簡單,卻藏著容易忽略的細節。本文透過同事的一段真實程式碼,說明 JavaScript sort 在處理相等元素時可能出現的「不穩定」問題,並提出可行的解法。
情境是這樣的:有一個由物件組成的陣列,屬性 a 是主要排序依據,屬性 b 是優先條件——當 b 等於 1 時,不論 a 是什麼都要排在最前面。同事的做法是「先按 a 排序,再按 b 排序」兩次 sort。問題就出在第二次。
直覺上我們會以為:第一次已按 a 由大到小排好,第二次只要把 b 等於 1 的元素提前、其餘不動即可(回傳 0 或 -1)。但這與語言採用的排序演算法有關。JavaScript 內建的 sort 是數種演算法的混合,並不保證相同元素的相對位置會維持不變,也就是所謂的 unstable(不穩定排序)。
以下例子可重現這個現象:
var arrayToSort = [
{name: 'a', strength: 1}, {name: 'b', strength: 1}, {name: 'c', strength: 1}, {name: 'd', strength: 1},
{name: 'e', strength: 1}, {name: 'f', strength: 1}, {name: 'g', strength: 1}, {name: 'h', strength: 1},
{name: 'i', strength: 1}, {name: 'j', strength: 1}, {name: 'k', strength: 1}, {name: 'l', strength: 1}
];
arrayToSort.sort(function (a, b) {
return b.strength - a.strength;
});
arrayToSort.forEach(function (element) {
console.log(element.name);
});
我們原以為輸出仍會是 a 到 l 的順序,實際執行卻是亂序的——因為 sort 沒有保留原陣列的順序。
那麼該如何避免?最直接的辦法是「把兩次 sort 的邏輯合併成一次」,在單一比較函式中同時考慮 a 與 b。如果因某些原因必須分多次排序,另一個做法是「把原始順序記錄在元素屬性上」,作為相等時的次要比較依據。理解排序穩定性的差異,能幫我們避開這類看似直覺卻充滿陷阱的 bug。