JavaScript中的好部分：排序不稳定？

Question

在《JavaScript语言精粹》一书中，作者在第81页提到了“稳定”的概念。链接至Google图书 然而，我发现书中给出的例子与排序是否稳定无关。维基百科 我有什么遗漏吗？

因此，书中的例子如下：

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Curly', last: 'Howard'}
];

The sort method is not stable, so:s.sort(by('first')).sort(by('last')); is not guaranteed to produce the correct sequence.

但是这个例子并没有证明排序是否稳定。如果先按照名字排序，再按照姓氏排序，那么按照名字排序的部分将被覆盖。结果如下：

[ { first: 'Joe', last: 'Besser' },
{ first: 'Joe', last: 'DeRita' },
{ first: 'Larry', last: 'Fine' },
{ first: 'Curly', last: 'Howard' },
{ first: 'Moe', last: 'Howard' },
{ first: 'Shemp', last: 'Howard' } ]

我知道JS的排序不保证稳定。这里和这里。但我认为这本书没有正确地处理这个话题。我的问题是，我不知道我的理解是否正确。如果我错了，我想知道为什么。

- theseadroid

---

那么你有什么问题？ - user1864610

我不确定我的理解是否正确。如果我错了，我想知道原因。 - theseadroid

@Claies：由于 sort(by('first'))，Howard 应该改变顺序。 - user2357112

@user245259 - 你应该编辑你的问题来真正地提出那个问题。;-) 在很大程度上，这并不是关于JavaScript（或ECMAScript）的，而是关于排序以及什么是非稳定排序的更好示例。 - RobG

我已经编辑了这个问题，使它更像一个问题。希望这样能满足那些投票关闭它的人。如果你觉得我的编辑没有抓住你原来问题的重点，请随意恢复它们。 - Joshua Carmody

Answer 1

假设你按名字排序，然后再按姓氏重新排序。你会得到类似这样的结果：

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    ?
    ?
    ?
]

前三个元素保证是那三个，但其余的元素呢？它们都有相同的姓氏 'Howard'，所以不清楚它们应该按什么顺序排列。

使用不稳定排序，这些项可以以任何顺序出现。你可能会得到以下结果：

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    { first: 'Shemp', last: 'Howard'}
    { first: 'Moe', last: 'Howard'},
    { first: 'Curly', last: 'Howard'},
]

最后三个元素按照名字的相反顺序排列。但是，使用稳定排序，这些元素将保证按照先前排序的顺序排列。按照名字排序，Curly排在Moe之前，Moe排在Shemp之前，因此您可以确保会按照以下顺序排列：

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    { first: 'Curly', last: 'Howard'},
    { first: 'Moe', last: 'Howard'},
    { first: 'Shemp', last: 'Howard'}
]

- user2357112

Answer 2

从您提供的链接中可以看出，“stable”是如何定义的，以及“Javascript: The Good Parts”的作者使用这个词的方式，我可以看出这本书似乎使用了稍微不同的定义。

作者的意思是，Javascript排序不是“稳定的”，因为您不能使用级联排序标准而不进行额外的编程工作。在其他一些语言中，您可以这样做。例如，在C#中，以下是有效的LINQ：

// Sorts by two columns at once, no overwriting.
var sorted = s.OrderBy(p => p.FirstName).ThenBy(p => p.LastName);

在我看来，当作者说“稳定”时，他的意思就是这样。

然而，你在问题中提供的维基和Mozilla文档表明，“稳定”排序不应该改变具有相同排序值的项目的相对顺序。因此，使用以下输入数据：

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Curly', last: 'Howard'}
];

如果我在Javascript中执行s.sort(by('last'));，并且它是稳定的，那么Moe Howard将始终排在Shemp Howard之前，Curly Howard将始终排在Shemp之后。排序只会考虑姓氏，这些人的姓氏相同，并且不会改变它们除此之外的相对顺序。如果您按姓氏对上述列表进行排序并获得以下结果：

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Curly', last: 'Howard'}
];

这意味着按照维基百科的定义，排序不是“稳定的”，因为Shemp、Moe和Curly相对位置发生了变化。

所以回答我认为你在问什么：《JavaScript: The Good Parts》中的代码并没有展示维基百科定义的排序不稳定性，因为作者显然是根据不同的单词定义进行操作的。

- Joshua Carmody

---

这两个“稳定（stable）”的定义完全等价。任何能满足其中一个保证的排序都必然同时满足另一个保证。 - user2357112

另外，请注意作者说：“sort方法不稳定，因此s.sort(by('first')).sort(by('last'))；不能保证产生正确的序列。”您可能会对OP所述的结果与稳定排序得到的结果相同感到困惑。 - user2357112