穩定的 Array.prototype.sort

發佈於 · 標籤為 ECMAScript ES2019

假設您有一個狗狗陣列，每個狗狗都有名字和評分。（如果這聽起來像個奇怪的範例，您應該知道有一個 Twitter 帳戶專門在做這件事… 別問！）

// Note how the array is pre-sorted alphabetically by `name`.
const doggos = [
  { name: 'Abby',   rating: 12 },
  { name: 'Bandit', rating: 13 },
  { name: 'Choco',  rating: 14 },
  { name: 'Daisy',  rating: 12 },
  { name: 'Elmo',   rating: 12 },
  { name: 'Falco',  rating: 13 },
  { name: 'Ghost',  rating: 14 },
];
// Sort the dogs by `rating` in descending order.
// (This updates `doggos` in place.)
doggos.sort((a, b) => b.rating - a.rating);

陣列預設會按名稱字母順序排序。若要改按評分排序（因此我們會先看到評分最高的狗狗），我們會使用 Array#sort，並傳入一個自訂的回呼函式來比較評分。這可能是您預期的結果

[
  { name: 'Choco',  rating: 14 },
  { name: 'Ghost',  rating: 14 },
  { name: 'Bandit', rating: 13 },
  { name: 'Falco',  rating: 13 },
  { name: 'Abby',   rating: 12 },
  { name: 'Daisy',  rating: 12 },
  { name: 'Elmo',   rating: 12 },
]

狗狗會按評分排序，但在每個評分內，牠們仍會按名稱字母順序排序。例如，Choco 和 Ghost 都有相同的評分 14，但 Choco 出現在 Ghost 之前，因為這也是牠們在原始陣列中的順序。

不過，要得到這個結果，JavaScript 引擎不能只使用任何排序演算法，它必須是所謂的「穩定排序」。很長一段時間以來，JavaScript 規格都沒有要求 Array#sort 的排序穩定性，而是交由實作決定。由於此行為未指定，您也可能會得到這個排序結果，其中 Ghost 突然出現在 Choco 之前

[
  { name: 'Ghost',  rating: 14 }, // 😢
  { name: 'Choco',  rating: 14 }, // 😢
  { name: 'Bandit', rating: 13 },
  { name: 'Falco',  rating: 13 },
  { name: 'Abby',   rating: 12 },
  { name: 'Daisy',  rating: 12 },
  { name: 'Elmo',   rating: 12 },
]

換句話說，JavaScript 開發人員無法依賴排序穩定性。實際上，情況甚至更令人惱怒，因為有些 JavaScript 引擎會對短陣列使用穩定排序，而對較長陣列使用不穩定排序。這真的很令人困惑，因為開發人員會測試他們的程式碼，看到穩定的結果，但當陣列稍微變大時，卻突然在實際環境中得到不穩定的結果。

但有好消息。我們 建議了一項規格變更，讓 Array#sort 變穩定，而且這項變更已被接受。所有主要的 JavaScript 引擎現在都實作了穩定的 Array#sort。這只是 JavaScript 開發人員少了一件需要擔心的問題。太棒了！

（喔，還有 我們對 TypedArray 做了同樣的事情：現在，這種排序也已穩定。）

注意：雖然現在規格要求穩定性，但 JavaScript 引擎仍然可以自由實作他們偏好的任何排序演算法。例如，V8 使用 Timsort。規格並未強制使用任何特定排序演算法。

功能支援 #

穩定的 Array.prototype.sort #

關於此功能支援清單

穩定的 %TypedArray%.prototype.sort #

關於此功能支援清單