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 中，保留具有相等值的元素的原始顺序。