javascript - 在 Chrome 中对对象数组进行排序

Question

编辑:正如下面 kennytm 所指出的，并在调查我自己之后，根据 ECMA spec ，当两个对象在自定义排序中被确定为相等时，JavaScript不需要使这两个对象保持相同的顺序。 Chrome 和 Opera 是仅有的两个选择具有不稳定排序的主要浏览器，但其他浏览器包括 Netscape 8&9、Kazehakaze、IceApe 等。 Chromium 团队已将此错误标记为“按预期工作”，因此不会“修复”它。如果您需要数组在值相等时保持原始顺序，则需要采用一些额外的机制(例如上面的机制)。对对象进行排序时返回 0 实际上是没有意义的，所以不必费心。或者使用支持稳定排序的库，例如 Underscore/Lodash。

<小时/>

我刚刚收到一份报告，称我编写的某些代码在 Chrome 上出现问题。我已经追踪到我用来对对象数组进行排序的自定义方法。我真的很想将此称为错误，但我不确定它是否是错误。

在所有其他浏览器中，当您对对象数组进行排序时，如果两个对象解析为相同的值，则它们在更新后的数组中的顺序将保持不变。在 Chrome 中，它们的顺序似乎是随机的。在 Chrome 和您想要的任何其他浏览器中运行以下代码。你应该明白我的意思。

我有两个问题:

首先，我的假设是否正确，当您的自定义排序器返回 0 时，两个比较的项目应该保持其原始顺序(我有一种感觉我错了)。

第二，有什么好的办法可以解决这个问题吗？我唯一能想到的是在排序之前向数组的每个成员添加一个自动递增数字作为属性，然后在两个项目 sort 将解析与相同值进行比较时使用该值。换句话说，永远不要返回 0。

这是示例代码:

var x = [
{'a':2,'b':1},
{'a':1,'b':2},
{'a':1,'b':3},
{'a':1,'b':4},
{'a':1,'b':5},
{'a':1,'b':6},
{'a':0,'b':7},
]

var customSort = function(a,b) {
    if (a.a === b.a) return 0;
    if (a.a > b.a) return 1;
    return -1;
};

console.log("before sorting");
for (var i = 0; i < x.length; i++) {
    console.log(x[i].b);
}
x.sort(customSort);

console.log("after sorting");
for (var i = 0; i < x.length; i++) {
    console.log(x[i].b);
}

在所有其他浏览器中，我看到只有数组的第一个成员和最后一个成员被移动(我看到7,2,3,4,5,6,1)但在 Chrome 中，内部数字似乎是随机的。

[编辑]非常感谢所有回答的人。我想“不一致”并不一定意味着它是一个错误。另外，我只是想指出我的 b 属性只是一个示例。事实上，我正在根据用户输入在大约 20 个键中的任意一个上对一些相对较宽的对象进行排序。即使跟踪用户上次排序的内容仍然无法解决我所看到的随机性问题。我的解决方法可能是与此类似的变体(突出显示新代码):

var x = [
{'a':2,'b':1},
{'a':1,'b':2},
{'a':1,'b':3},
{'a':1,'b':4},
{'a':1,'b':5},
{'a':1,'b':6},
{'a':0,'b':7},
];
var i;

var customSort = function(a,b) {
    if (a.a === b.a) return a.customSortKey > b.customSortKey ? 1 : -1; /*NEW CODE*/
    if (a.a > b.a) return 1;
    return -1;
};

console.log("before sorting");
for (i = 0; i < x.length; i++) {console.log(x[i].b);}

for (i = 0; i < x.length; i++) {                      /*NEW CODE*/
    x[i].customSortKey = i;                           /*NEW CODE*/
}                                                     /*NEW CODE*/
x.sort(customSort);

console.log("after sorting");
for (i = 0; i < x.length; i++) {console.log(x[i].b);}

Answer 1

ECMAScript 标准 does not guarantee Array.sort is a stable sort 。 Chrome(V8 引擎)使用 in-place QuickSort internally (对于大小 ≥ 22 的数组，否则插入排序)速度很快，但 not stable .

要修复此问题，请将 customSort 也与 .b 进行比较，从而消除排序算法稳定性的需要。