Crockford-数组排序-页面81 [英] Crockford - array sorting - page 81

问题描述

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领先 大批.我没有在本书的勘误表中找到这个.

When I actually execute this code, in the sorted array, Joe DeRitta comes after Joe Besser which kind of makes more sense as this is the order in which they come in the original array. The author says DeRita comes before Besser in the sorted array. I don't find this in the errata of the book.

(1)这是一些错字吗(我怀疑，我猜代码已经运行了) 或只是最近"的另一件事(在 最近5-6年)更改了JavaScript?

(1) Is this some typo (I doubt it, I guess the code was run) or just another thing which is a "recent" (implemented in the last 5-6 years) change in JavaScript?

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

(2) Down below the author says: "The sort method is not stable, so:

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

不能保证产生正确的序列."

is not guaranteed to produce the correct sequence."

这真的是关于稳定排序的吗? http://en.wikipedia.org/wiki/Category:Stable_sorts 我认为这本书发生了两种连续的变化， 而且它们几乎没有机会按正确的顺序进行排序， 但是我认为这与稳定排序"的概念无关. 是吗?

Is that really what stable sort is about? http://en.wikipedia.org/wiki/Category:Stable_sorts I think what happens in the book is two consecutive sorts, and there's no much chance these to sort in the proper order, but I think this is not related to the concept of "stable sort". Is it?

想象一下这两个名字:

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

如果我们按名字排序，那么阿尔弗雷德将永远是第一名. 如果我们按姓氏排序，芭芭拉将永远是第一位. 所以...如果我们这样做:

If we sort by first name, Alfred will be always first. If we sort by last name, Barbara will be always first. So... if we do:

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

结果将仅取决于我们最后的排序方式(在这种情况下， 我们按姓氏排序).

the result will only depend on what we sort last by (in this case we sort last by last name).

我误解了吗(好的，我承认我没有考虑过 最近的稳定排序)，即这里提到的稳定排序有什么用?

Am I misunderstanding something (OK, I admit I haven't thought about stable sorts recently) i.e. what's the stable sort mentioned here for?

推荐答案

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

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

I think what happens in the book is two consecutive sorts

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

That's exactly correct. If that code was invoked, then the list would first be sorted completely by first name, then completely resorted by last name.

但是我认为这与稳定排序"的概念无关.是吗?

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

实际上，有关系. 稳定的排序算法将遵循以下规则:

Actually, there is a relation. A stable sorting algorithm will obey the following rule:

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

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')) (如果使用稳定的排序算法)将比较姓氏"Howard"和"Howard"，确定姓氏相等，并保留原始顺序 >.这意味着姓氏相同的所有项目都将保留按名字排序时产生的顺序.

In your example, consider the names "Shemp Howard" and "Curly Howard". If the sorting algorithm were stable, and you wanted the list of names to be sorted by last name then first name, you could invoke two subsequent sorts. s.sort(by('first')) will put those two items in the order: Curly Howard, Shemp Howard. Subsequently invoking s.sort(by('last')) if using a stable sorting algorithm will compare that last names "Howard" and "Howard", determine that the last names are equal, and preserve the original order. That means that any items that have an equal last name would remain in the order that resulted when sorting by first name.

不幸的是，正如Crockford所述，javascript的 Array.sort不一定是稳定的，并且随后的两个排序也不能保证等价项保持其原始顺序.

Unfortunately, as noted by Crockford, javascript's Array.sort is not necessarily stable, and two subsequent sorts will have no guarantee of keeping equivalent items in their original order.

这篇关于Crockford-数组排序-页面81的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！