Javascript的好部分:排序不稳定？

Question

在"Javascript: the Good Parts“一书中，作者在第81页提到了”稳定“的概念。链接到谷歌图书

然而，我发现这本书给出的例子与排序是否稳定无关。维基

我在这里有遗漏什么吗？

因此，书中的例子如下：

var s= {first：'Joe‘}，{first：'Moe’}，{first：‘Moe’}，{first：'Joe‘}，{first：'DeRita'}，{first：'Shemp'，最后一个：'Howard'}，{first：'Larry'，最后一个：’罚款‘}，{first：'Curly'，'Howard'}； 排序方法不稳定，因此:不能保证s.sort(by('first')).sort(by('last'));生成正确的序列。

但是这个例子实际上不能证明排序是否稳定。如果先排序然后按最后排序，则按第一部分排序将被覆盖。结果如下：

[ { 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排序不能保证稳定。这里和这里.但我认为这本书并没有以正确的方式对待这个主题。我的问题是，我不知道我的理解是否正确。如果我错了我想知道为什么。

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的前面，他领先于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'}
]

Answer 2

看看你提供的链接是如何定义“稳定”的，以及"Javascript: Good Parts“的作者是如何使用这个词的，我可以看到这本书确实使用了一个稍微不同的定义。

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

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

在我看来，这就是作者所说的“稳定”的意思。

但是，您在问题中链接到的Wiki和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将总是列在Shemp之前，而Curly总是在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: Good Parts“中的代码没有表现出维基百科定义的排序不稳定，因为作者显然是在对这个词的不同定义下操作的。