稳定的 Array.prototype.sort

发布 · 标签：ECMAScript ES2019

假设你有一个狗狗数组，每个狗狗都有名字和评分。（如果这听起来像个奇怪的例子，你应该知道有一个专门做这个的推特账号……别问！）

// 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 #

关于此特性支持列表