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）これはタイプミス（おそらくコードが実行されたと思います）ですか、それとも「最近の」（過去5〜6年に実装された）JavaScriptの別の変更ですか？

(2) 著者の下には、「ソート方法が安定していないため、

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

正しいシーケンスを生成する保証はありません。」

それは本当に安定したソートのことですか？ http://en.wikipedia.org/wiki/Category:Stable_sorts この本の中で起こっているのは 2 つの連続した並べ替えであり、これらが適切な順序で並べ替えられる可能性はあまりないと思いますが、これは概念とは関係ないと思います「安定したソート」の。それは...ですか？

次の 2 つの名前を想像してください。

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

名で並べ替えると、Alfred が常に最初になります。姓で並べ替えると、Barbara が常に最初になります。だから...もしそうなら：

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

結果は、最後に並べ替えた基準にのみ依存します (この場合、姓で最後に並べ替えます)。

私は何かを誤解していますか (わかりました、私は最近安定した並べ替えについて考えていないことを認めます) つまり、ここで言及されている安定した並べ替えは何ですか?

4

1 に答える 1

2

s.sort(by('first')).sort(by('last'));あなたが言うコードに関して：

本で起こることは2つの連続した種類だと思います

その通りです。そのコードが呼び出された場合、リストは最初に名前で完全にソートされ、次に姓で完全に並べ替えられます。

しかし、これは「安定ソート」の概念とは関係ないと思います。それは...ですか？

実は関係があるんです。安定したソート アルゴリズムは、次の規則に従います。

2 つの項目を比較して等しい場合、それらの相対的な順序は保持されるため、一方が入力で他方より前にある場合、出力でも他方より前になります。

あなたの例では、「Shemp Howard」と「Curly Howard」という名前を考えてみましょう。並べ替えアルゴリズムが安定していて、名前のリストを姓、名の順で並べ替えたい場合は、2 つの後続の並べ替えを呼び出すことができます。s.sort(by('first'))カーリー ハワード、シェンプ ハワードの 2 つの項目を順番に並べます。s.sort(by('last')) その後、安定した並べ替えアルゴリズムを使用して if を呼び出すと、姓の "Howard" と "Howard" が比較され、姓が等しいことが判断され、元の順序が維持されます。つまり、姓が同じ項目は、名でソートしたときの順序のままになります。

残念ながら、Crockford が指摘したように、javascript のArray.sort は必ずしも安定しているとは限らず、その後の 2 つの並べ替えでは、同等のアイテムが元の順序で保持される保証はありません。

于 2013-10-18T20:22:03.640 に答える