随后的多维数组排序会产生意外的结果

Subsequent sort of multidimensional arrays yields unexpected results

本文关键字:意外 结果 数组排序      更新时间:2023-09-26

我有一个排序异常,我可以在Chrome版本28.0.1500.71 Ubuntu 12.04(28.0.1500.71-0ubuntu1.12.04.1)中重现,这是我今天可以使用的全部内容,但我在Firefox的最新版本中也看到了相同的结果。

给定以下代码:

<SCRIPT type="text/javascript">
var ary=[];
for(var x=0; x<11; x++){
    var tmp=[];
    tmp[0]="COL" + ("00" + x).substr(-3);
    tmp[1]= Math.floor(x/3);
    ary[x]=tmp;
}
ary.sort(function(a,b){
    if(a[0]>b[0]){return 1}
    if(a[0]<b[0]){return -1}
    return 0;
});
console.log(ary.toString());
ary.sort(function(a,b){
    if(a[1]>b[1]){return 1}
    if(a[1]<b[1]){return -1}
    return 0;
});
console.log(ary.toString());
</SCRIPT>

正如您(可能)看到的,第一次排序的结果显示ary[]按列0正确排序,但在第二次排序之后,当a[1]=b[1]时,以前执行的排序现在(可能)颠倒了。

如果x的迭代次数较少,则第二次排序(可能)会返回预期结果。

我已经看到这一点有一段时间了,但现在我需要能够按一个任意列,然后按另一列,然后再按另一个列,对多达15000行进行排序,而不会在a[?]==b[?]时丢失以前排序的排序顺序。我认为这是意料之中的行为。

我猜这是javascript排序算法中内置的一个节省时间的功能,但有一个不可预见的副作用。

当当前排序中的a==b时,有没有一个神奇的子弹可以让我不必循环遍历以前的每个排序?

编辑:@阿米尔:好吧,这是一个可行的"灵丹妙药"吗

我们可以向数组中添加一个索引值,当我们进行排序时,如果我们的值相等,我们就可以根据索引本身进行排序。

for(var x=0; x<ary.length; x++){ary[x].index = x;}
ary.sort(function(a,b){
    if(a[2]>b[2]){return 1;}
    if(a[2]<b[2]){return -1;}
    if(a.index>b.index){
        return 1;
    }
    return -1;
});

当我们放入索引时,我们可以知道上一次排序对数组做了什么,并在当前排序中保持a[?]=b[?]的排序顺序。

我想知道这有多快——我也想知道如何在排序过程中对索引进行重新编号,而不是在每次排序之前重新创建索引,但我担心这会使值相等的排序失败。也许我们可以添加一个在排序过程中更改的newIndex属性,然后将index的值设置为newIndex值。

有什么建议吗?

问题是javascript中的排序不能保证稳定(如果元素相等,则不能保证保留元素的顺序)请参阅此处