DIV CSS 佈局教程網

連用兩次 sort 為什麼會出錯?談 JavaScript 排序的穩定性
編輯:關於JavaScript     

前不久同事的程式裡出現一個很離奇的問題。需求本身並不難:對一個由物件組成的陣列排序,屬性 a 是主要排序依據,屬性 b 則是優先條件——當 b 等於 1 時,不論 a 是多少都要排到最前面。

他的作法是跑兩次 sort:先依 a 排序,再依 b 的值排序。問題就出在第二次。

錯在哪裡

直覺上會認為:第一次排序後陣列已依 a 由大到小排好,第二次只要「不動到原有順序」(比較函數固定回傳 0 或 -1),單獨把 b 等於 1 的挑到前面就好。

但這裡隱含一個前提:排序必須是穩定的,也就是相等元素在排序前後的相對位置不變。JavaScript(以及其他許多語言)內建的 sort 並非總是穩定排序——引擎往往依資料量在插入排序、合併排序、快速排序之間切換,而後者並不保證保留原序。

一個可重現的例子

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},
  {name: 'm', strength: 1}, {name: 'n', strength: 1}, {name: 'o', strength: 1}, {name: 'p', strength: 1},
  {name: 'q', strength: 1}, {name: 'r', strength: 1}, {name: 's', strength: 1}, {name: 't', strength: 1}
];

arrayToSort.sort(function (a, b) {
  return b.strength - a.strength;
});

arrayToSort.forEach(function (element) {
  console.log(element.name);
});

所有元素的 strength 都相同,照理說排序後應該仍是 a 到 t 的順序,實際執行卻是亂序的——這就是 unstable 的具體表現。

怎麼避免

最直接的辦法是把多次排序合併成一次。以同事的案例來說,只要在比較函數裡先判斷 b,b 為 1 的優先;b 相同時再比 a,一次就能排出正確結果:

arrayToSort.sort(function (x, y) {
  if (x.b !== y.b) { return y.b - x.b; }  // b 為 1 的排前面
  return y.a - x.a;                       // 再依 a 排序
});

如果業務邏輯實在必須分多趟排序,那就把原始順序當成一個欄位記在元素上,並在比較函數的最後一層拿它當 tie-breaker。別把「引擎應該會保留原序」當成可以依賴的假設。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved