2 
var by = function (name) {
    return function (o, p) {
        var a, b;
        if (typeof o === 'object' && typeof p === 'object' && o && p) {
            a = o[name];
            b = p[name];
            if (a === b) {
                return 0;
            }
            if (typeof a === typeof b) {
                return a < b ? -1 : 1;
            }
            return typeof a < typeof b ? -1 : 1;
        } else {
            throw {
                name: 'Error',
                message: 'Expected an object when sorting by ' + name
            };
        }
    };
};

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'}
];


s.sort(by('first'));// s is [
// {first: 'Curly', last: 'Howard'},
// {first: 'Joe', last: 'DeRita'},
// {first: 'Joe', last: 'Besser'},
// {first: 'Larry', last: 'Fine'},
// {first: 'Moe', last: 'Howard'},
// {first: 'Shemp', last: 'Howard'}
// ]

当我实际执行此代码时，在排序后的数组中，Joe DeRitta 出现在 Joe Besser 之后，这更有意义，因为这是它们在原始数组中出现的顺序。作者说 DeRita 在排序数组中排在 Besser 之前。我在本书的勘误表中没有找到这个。

（1）这是一些错字（我怀疑，我猜代码已经运行）还是只是 JavaScript 中“最近”（在过去 5-6 年内实施）变化的另一件事？

(2) 下面作者说：“排序方法不稳定，所以：

s.sort(by('first')).sort(by('last'));

不能保证产生正确的序列。”

这真的是稳定排序的意义所在吗？ http://en.wikipedia.org/wiki/Category:Stable_sorts 我认为书中发生的事情是两个连续的排序，并且没有太多机会按正确的顺序排序，但我认为这与概念无关的“稳定排序”。是吗？

想象一下这两个名字：

[
    { first: "Alfred", last: "Williams" },
    { first: "Barbara", last: "Charles" }
]

如果我们按名字排序，Alfred 将永远是第一个。如果我们按姓氏排序，芭芭拉永远是第一位的。所以......如果我们这样做：

s.sort(by('first')).sort(by('last'));

结果将仅取决于我们最后排序的内容（在这种情况下，我们按姓氏排序）。

我是不是误解了什么（好吧，我承认我最近没有考虑过稳定排序），即这里提到的稳定排序是什么？

4

1 回答 1

2

关于s.sort(by('first')).sort(by('last'));你说的代码：

我认为书中发生的事情是两种连续的

这是完全正确的。如果调用该代码，则列表将首先完全按名字排序，然后完全按姓氏排序。

但我认为这与“稳定排序”的概念无关。是吗？

其实是有关系的。一个稳定的排序算法将遵循以下规则：

如果两个项目比较相等，那么它们的相对顺序将被保留，因此如果一个在输入中排在另一个之前，那么它在输出中也将排在另一个之前。

在您的示例中，考虑名称“Shemp Howard”和“Curly Howard”。如果排序算法是稳定的，并且您希望按姓氏然后名字对名称列表进行排序，则可以调用两个后续排序。s.sort(by('first'))将把这两个项目按顺序排列：Curly Howard、Shemp Howard。s.sort(by('last')) 如果使用稳定的排序算法，随后调用将比较姓氏“霍华德”和“霍华德”，确定姓氏相等，并保留原始顺序。这意味着具有相同姓氏的任何项目都将保持按名字排序时的顺序。

不幸的是，正如 Crockford 所指出的，javascript 的Array.sort 不一定是 stable，随后的两个排序将无法保证将等价项目保持在其原始顺序中。

于 2013-10-18T20:22:03.640 回答