为什么我的Javascript程序中的Array.sort(）方法不稳定

Why is the Array.sort() method in my Javascript program unstable?

本文关键字：sort 方法 不稳定 Array 我的 Javascript 程序 为什么      更新时间：2023-09-26

这是我的jsFiddle:

//Change this variable to change the number of players sorted
var numberOfPlayers = 15;
var teams = [];
var alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for(var a=0; a<numberOfPlayers; a++){
  updateStandings();
    teams.push(new Team(alphabet.charAt(a)));
}
console.log("Teams:");
for(var x=0; x<teams.length; x++){
    console.log(teams[x].name);
}
//Functions and such
function updateStandings(){
  teams.sort(function(a, b) { 
    if(a.score == b.score){ 
      if(a.tiebreak == b.tiebreak){
        return teams.indexOf(a)-teams.indexOf(b);
      }else{
        return b.tiebreak-a.tiebreak;
      }
    }else{
      return b.score-a.score;
    }
  });
}
function Team(name){
  this.name = name;
  this.score = 0;
  this.tiebreak = 0;
}

我认为问题是javascript排序不稳定，并更改了比较函数，但它仍然不起作用。

JS中稳定排序的通用方法如下：

function stable_sort(array, sortfunc) {
  function _sortfunc(a, b) { return sortfunc(array[a], array[b]) || a - b; }
  return array.map((e, i) => i) . sort(_sortfunc) . map(i => array[i]);
}

这实际上是对索引列表进行排序。然后，它将已排序的索引列表映射回原始数组。排序函数被重写以比较数组中那些索引处的值，如果它们相等，则返回到索引本身的比较。

这种方法避免了代码中的问题，即它正在对处于排序中间的数组进行indexOf查找。

这个问题可能会提供信息。

根据文档，排序方法不需要稳定：https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort在某些浏览器中它是稳定的，而在某些浏览器则不然。

您确实需要更改比较函数，但不要像您尝试的那样。原因是你比较

return teams.indexOf(a)-teams.indexOf(b);

在电流阵列中。这意味着，如果a和b的顺序在前面的步骤中发生了变化，则排序例程将保留这个新顺序，而不是这些元素一开始的顺序。

有不同的方法来解决它。例如，您可以在排序之前创建数组的副本，并在此副本上执行indexOf。它将保留元素在开始排序之前的顺序。

但如果你事先知道订单，你也可以运用这些知识。例如，如果在排序之前，团队是按名称排序的，那么您可以将名称作为字符串而不是数组中的位置进行比较，这将比第一个选项高效得多。

因为JS的排序通常不稳定。规范§22.1.3.24：

此数组的元素已排序。排序不一定是稳定的（也就是说，比较相等的元素不一定保持其原始顺序）。

您的团队创建时除了名称外具有相同的属性，因此实际执行排序的行是：

return teams.indexOf(a)-teams.indexOf(b);

因为您调用的是indexOf，所以它在每次重复排序时都会搜索项（及其索引）。排序会使数组发生变化（来自MDN：它"将数组的元素排序到适当的位置并返回数组"）。

您正在排序的同一数组中搜索项，因此索引可能会在每次迭代中更改。如果做得正确（相对而言），你可以用它产生一种永无止境的东西。

例如：

const data = [1, 3, 2, 4];
let reps = 0;
data.sort((a, b) => {
  console.log(data);
  
  const ia = data.indexOf(a), ib = data.indexOf(b);
  if (ia === ib || reps > 50) {
    return 0;
  } else if (ia < ib) {
    return 1;
  } else if (ib < ia) {
    return -1;
  }    
});

相关文章：