Javascript排序函数错误地更改了元素在数组中的位置

Question

我正在使用我的AngularJS应用程序的数组排序功能.它使用变量,, direction来确定是以升序(direction === -1)还是降序(direction === 1)方式对数据进行排序.

出了什么问题:有时当我进行排序时,数组中应该位于相同位置的元素将返回到不同的位置,而数组中的任何内容实际上都没有变化.

例如,如果我有:

   var arr = [
       {id: 3, name: 'd'},
       {id: 2, name: 'b'},
       {id: 1, name: 'a'},
       {id: 2, name: 'c'}
   ];

然后我按照"id"的方向对它进行排序-1,它将以你所期望的名称返回"a,b,c,d".然后我会再次排序(改变方向1),它将反转方向.但是如果我再次对它进行排序(带direction === -1),它将以"a,c,b,d"的顺序返回.

这是一个简化的例子; 实际上它远没有那么可预测.

我有一种感觉,我没有direction正确使用我的排序.见下文:

this.sortData = function (data, type, direction) {

    return data.sort(sortFunct);

    function sortFunct(a, b) {
        var numberTypes = ['Thread', 'Job', 'FolderCount', 'MessageCount', 'EmailCount', 'CalendarCount', 'TaskCount', 'OtherCount', 'JobId', 'BatchId', 'ItemsTotal', 'ItemsRemaining', 'ItemsFailed', 'Size', 'progress', 'PercentComplete'];
        var stringTypes = ['Level', 'StatusMessage', 'Author', 'ItemStatus', 'JobStatus', 'SourceMailbox', 'TargetMailbox', 'Subject', 'Folder', 'MessageClass', 'StatusMessage', 'Path', 'Owner1',];

        if (numberTypes.indexOf(type) !== -1) {
            return direction * (a[type] - b[type]);
        } else if (stringTypes.indexOf(type) !== -1) {
            if (!a[type]) {
                return 1;
            } else if (!b[type]) {
                return -1;
            } else {
                return a[type].localeCompare(b[type]) * direction;
            }
        } else if (type === 'DiscoveryDate' || type === 'ReceivedDate' || type === 'Timestamp') {
            if (a[type] > b[type]) {
                return direction * 1;
            } else if (a[type] < b[type]) {
                return direction * -1;
            } else {
                return 0;
            }
        } else {
            return direction * (a[type] - b[type]);
        }
    } // End sortFunct
};

Answer 1

ECMAScript规范.sort()并不要求它是稳定的,因此你的自定义排序函数所说的元素是相同的(例如,返回0)将不会相互保证顺序,事实上,它们最终的顺序可能是在排序之前受到他们所处的顺序的影响.

如果你想要一致的排序,那么你需要永远不要0从你的自定义排序函数返回,除非这两个项完全相同,这样你就永远不知道哪个是哪个.

当主键相同时,您需要测试辅助键并返回该比较的结果.如果辅助键是相同的,那么比较一个三级键等等,只要它值得你去.

这种二次比较可以使排序稳定,以便它始终以可预测的顺序着陆,无论之前的顺序如何.

我也看到了排序方案,它创建了一个唯一的密钥,并将其分配给每个对象,并将其用作二级或三级密钥,从而保证如果您关心的密钥相同,则可以比较唯一密钥并始终有一致的稳定排序.

以下是如果比较字段(此时的年龄具有相同值),则保留原始订单的方案示例.要知道原始订单是什么,它会使用origOrder标识原始订单的属性标记每个对象.

var data = [
  {name: "Amy", age: 13},
  {name: "Anne", age: 13},
  {name: "John", age: 11},
  {name: "Jack", age: 12},
  {name: "Ted", age: 11},
  {name: "Alice", age: 12}
];
  
// mark each object with the original order  
data.forEach(function(item, index) {
  item.origOrder = index;
});  
  
data.sort(function(a, b) {
  var diff = a.age - b.age;
  if (diff !== 0) {
    return diff;
  } else {
    return a.origOrder - b.origOrder;
  }
});  

// show results in snippet
document.write(JSON.stringify(data));  

使用ES6中的Map对象,我们也可以在不触及数组中的原始对象的情况下通过创建临时索引来执行此操作,该索引用于解析关系并将其存储在Map对象中.这可能是这样的:

    var data = [
      {name: "Amy", age: 13},
      {name: "Anne", age: 13},
      {name: "John", age: 11},
      {name: "Jack", age: 12},
      {name: "Ted", age: 11},
      {name: "Alice", age: 12}
    ];
    
    // put each object in a temporary map with its original index
    let tempMap = new Map();
    data.forEach((item, index) => {
        tempMap.set(item, index);
    });
      
    data.sort(function(a, b) {
      var diff = a.age - b.age;
      if (diff !== 0) {
        return diff;
      } else {
        return tempMap.get(a) - tempMap.get(b);
      }
    });  

    // show results in snippet
    document.write(JSON.stringify(data));  

通过查看排序结果,您可以看到保留两个具有相同年龄的条目的相对顺序,而无需以任何方式修改原始对象.