0

我需要对一个数组进行排序，但它只能在 Chrome 中正常工作。在 Mozilla 规范中我找到了这个文本，但仍然无法解决这个问题：

“这个数组的元素是排序的。排序不一定是稳定的（也就是说，比较相等的元素不一定保持原来的顺序）。如果 comparefn 不是未定义的，它应该是一个接受两个参数 x 和如果 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 中的排序：每个比较函数都应该有一个“return 0”语句吗？

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

这不是一个一致的比较函数（例如，违反了自反性compare(x, x) == 0）。你期望它做什么？

引用ES5.1 规范sort：

如果comparefnis [...] 不是此数组元素的一致比较函数，则排序的行为是实现定义的。

如果集合中的所有值、和（可能相同的值）都满足以下所有要求，则函数是comparefn一组值的一致比较函数：手段（任一标志）；和手段。SabcSa <CF bcomparefn(a,b) < 0a =CF bcomparefn(a,b) = 0a >CF bcomparefn(a,b) > 0

当给定一对特定的值并作为它的两个参数时，调用comparefn(a,b)总是返回相同的值。此外，is Number，而不是。请注意，这意味着 , 和 中的一个对于给定的 和 将是正确的。vabType(v)vNaNa <CF ba =CF ba >CF bab

  • 调用comparefn(a,b)不会修改 this 对象。
  • 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

我的另一个答案解释了为什么您的排序工作不稳定。这将解决您的实际问题:-)

您不能将 asort用于此类问题，您希望从（无序的）边集构建节点列表。仅当您可以在没有额外数据的情况下比较两个元素时，才能对数组进行排序。假设您只有两个连接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 回答