JavaScript 中的穩定排序演算法

對資料進行排序時，保留相等元素的原始順序對於穩定的排序演算法至關重要。在這種情況下，我們的目標是按給定順序對具有特定鍵的物件陣列進行排序，同時保持元素順序一致性。

穩定排序技術

有趣的是，甚至非穩定排序函數可以實現穩定排序。透過在排序前捕捉每個元素的初始位置，我們可以使用位置作為次要標準來打破排序比較中的平局。

JavaScript 中的實作

const sortBy = (arr, key, order) => {
  // Capture element positions
  const positions = arr.map((item, i) => {
    return { item, position: i };
  });

  // Perform sorting
  positions.sort((a, b) => {
    let cmp = a.item[key].localeCompare(b.item[key]);
    if (cmp === 0) {
      // Tiebreaker: sort by position
      cmp = a.position - b.position;
    }
    if (order === "desc") {
      return cmp * -1;
    } else {
      return cmp;
    }
  });

  // Return sorted objects
  return positions.map(position => position.item);
};

用法範例

const data = [
  { name: "Alice", age: 25 },
  { name: "Bob", age: 30 },
  { name: "Eve", age: 25 },
];

const sortedAscending = sortBy(data, "age", "asc");
console.log(sortedAscending); // [{ name: "Alice", age: 25 }, { name: "Eve", age: 25 }, { name: "Bob", age: 30 }]

const sortedDescending = sortBy(data, "age", "desc");
console.log(sortedDescending); // [{ name: "Bob", age: 30 }, { name: "Eve", age: 25 }, { name: "Alice", age: 25 }]

這種技術可以實現穩定的排序在JavaScript 中，保留具有相等值的元素的原始順序。