javascript - Crockford - 数组排序 - 第 81 页

Question

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) 这是不是打错了(我怀疑，我猜代码已经运行了)或者只是另一件“最近”的事情(在过去 5-6 年)JavaScript 的变化？

(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'));

结果将仅取决于我们最后排序的内容(在本例中我们按姓氏排序)。

我是不是误会了什么(好吧，我承认我没有想过最近稳定排序)即这里提到的稳定排序是什么？

Answer 1

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

I think what happens in the book is two consecutive sorts

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

but I think this is not related to the concept of "stable sort". Is it?

其实是有关系的。 stable sorting algorithm将遵守以下规则:

If two items compare as equal, then their relative order will be preserved, so that if one came before the other in the input, it will also come before the other in the output.

在您的示例中，考虑名称“Shemp Howard”和“Curly Howard”。 如果排序算法是稳定的，并且您希望名称列表按姓然后名排序，您可以调用两个后续排序。 s.sort(by('first')) 会将这两项按顺序排列:Curly Howard、Shemp Howard。随后调用 s.sort(by('last')) if using a stable sorting algorithm 将比较姓氏“Howard”和“Howard”，确定最后一个名称相等，并且保留原始顺序。这意味着任何具有相同姓氏的项目都将保留按名字排序时产生的顺序。

不幸的是，正如 Crockford 所指出的，javascript 的 Array.sort is not necessarily stable , 并且随后的两个排序将无法保证将等同的项目保持在其原始顺序中。