0

1つの配列を並べ替える必要がありますが、Chromeでのみ正しく機能します。mozilla仕様で私はこのテキストを見つけましたが、それでもこれを修正することはできません：

「この配列の要素は並べ替えられます。並べ替えは必ずしも安定していません（つまり、等しいと比較する要素は必ずしも元の順序のままではありません）。comparefnが未定義でない場合は、2つの引数xとを受け入れる関数である必要があります。 yであり、x <yの場合は負の値、x = yの場合はゼロ、x>yの場合は正の値を返します。」

そしてこのリンクhttps://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/sort はあなたと私を助けるかもしれません

これは私のコードです

arr.sort(sortTrip); 

function sortTrip(a, b) {   

    if (a.to != b.from) return 1;
    if (a.to == b.from) return -1;

}

そしてこれはarr：

var arr = [
    {
        "from": "Moscow",
        "to": "Rome",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Oslo",
        "to": "Paris",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Helsinki",
        "to": "Tokio",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Tokio",
        "to": "Moscow",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Paris",
        "to": "New-York",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Rome",
        "to": "Oslo",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    }
]

結果は

  • ヘルシンキ-トキオ
  • 東京-モスクワ
  • モスクワ-ローマ
  • ローマ-オスロ
  • オスロ-パリ
  • パリ-ニューヨーク
4

2 に答える 2

4

JavaScriptでの並べ替えも参照してください。すべての比較関数に「return0」ステートメントを含める必要がありますか？

if (a.to != b.from) return 1;
if (a.to == b.from) return -1;

これは一貫した比較関数ではありません（compare(x, x) == 0たとえば、反射性に違反します）。あなたはそれが何をすることを期待していますか？

ES5.1仕様sortの引用：

が[…]この配列の要素の一貫した比較関数でない場合comparefn、ソートの動作は実装によって定義されます。

関数は、セット内のすべての値、、、および（おそらく同じ値）について以下のすべての要件が満たされている場合comparefn、値のセットに対する一貫した比較関数です。表記は;を意味します。（いずれかの記号の）を意味します。とは。SabcSa <CF bcomparefn(a,b) < 0a =CF bcomparefn(a,b) = 0a >CF bcomparefn(a,b) > 0

特定の値のペアが指定された場合、およびその2つの引数として、呼び出しcomparefn(a,b)は常に同じ値を返します。さらに、はNumberであり、ではありません。これは、、、のいずれかが、との特定のペアに対して真になることを意味することに注意してください。vabType(v)vNaNa <CF ba =CF ba >CF bab

  • 呼び出しcomparefn(a,b)ても、このオブジェクトは変更されません。
  • a =CF a（再帰性）
  • の場合a =CF b、b =CF a（対称性）
  • a =CF bとの場合b =CF c、a =CF c（の推移性=CF）
  • a <CF bとの場合b <CF c、a <CF c（の推移性<CF）
  • a >CF bとの場合b >CF c、a >CF c（の推移性>CF）

注：上記の条件はcomparefn、セットSを同値類に分割し、これらの同値類が完全に順序付けられていることを保証するために必要かつ十分です。

于 2013-03-24T15:59:28.710 に答える
0

私の他の答えは、あなたのソートが安定して機能しない理由を説明しています。これはあなたの実際の問題を解決します:-)

sort（順序付けされていない）エッジのセットからノードのリストを作成するこのタイプの問題には、を使用できません。配列の並べ替えは、追加のデータなしで2つの要素を比較できる場合にのみ適用できます。接続が2つしかない場合、どちらが先に来るかわかりません（計画に連絡しないと、まだ接続がありません）Tokio - Moscow。Rome - Oslo対照的に、数値を比較する場合、（差を計算することにより）5が3より大きいことを簡単かつ常に判断できます。

代わりに、次のようなことを行う必要があります。名前でステーションに簡単にアクセスできる構造を構築し、ループ中に接続に遭遇したときに直接接続を挿入して、最終的にステーションごとの接続のリストを作成します。

var map = {};
for (var i=0; i<arr.length; i++) {
    var con = arr[i];
    map[con.from] = con;
}

これで、ルートをある種のリンクリストとして作成できるようになります。

for (var from in map) {
    var connTo = map[from].to;
    if (connTo in map)
        map[from].next = map[connTo];
}

そして、地図からすべての目的地を削除して、スタートステーションを見つけます。

for (var from in map)
    for (var next = map[from]; next; next = next.next)
         delete map[next.to];
for (from in map) // there's only one key left
    var start = from; // "Helsinki"

駅名の配列としてルートを作成しましょう。

var route = [start],
    conn = map[start];
while (conn) {
    route.push(conn.to)
    conn = conn.next;
    // maybe delete conn.next as we don't need it any more
}
// route:
// ["Helsinki", "Tokio", "Moscow", "Rome", "Oslo", "Paris", "New-York"]

または必要な結果、接続のリスト：

var arr = [];
for (var conn = map[start]; conn; conn = conn.next)
    arr.push(conn);

その計画があれば、元の配列をソートするための比較関数を作成することもできます。

arr.sort(function(a, b) {
    // compare the positions of the departure stations in the route
    return route.indexOf(a.from) - route.indexOf(b.from);
});
于 2013-03-24T17:58:58.470 に答える