在Array.sort的这个中间阶段发生了什么？

Question

在对数组方法进行深入研究时,我决定查看Array.sort方法中涉及的步骤.看看这段代码来反转数组的顺序:

let arr = [];

for (let i = 1; i < 6; i++) {
  arr.push(i);
}

arr.sort((value1, value2) => {
  console.log(arr);
  console.log(`Comparing ${value1} : ${value2}`);
  return value2 - value1;
});

console.log(arr);

我得到这个输出:

[1, 2, 3, 4, 5]
Comparing 1 : 2
[2, 1, 3, 4, 5]
Comparing 1 : 3
[2, 1, 1, 4, 5]
Comparing 2 : 3
[3, 2, 1, 4, 5]
Comparing 1 : 4
[3, 2, 1, 1, 5]
Comparing 2 : 4
[3, 2, 2, 1, 5]
Comparing 3 : 4
[4, 3, 2, 1, 5]
Comparing 1 : 5
[4, 3, 2, 1, 1]
Comparing 2 : 5
[4, 3, 2, 2, 1]
Comparing 3 : 5
[4, 3, 3, 2, 1]
Comparing 4 : 5
[5, 4, 3, 2, 1]

前两个步骤是有道理的,但看看第三个:[2, 1, 1, 4, 5].

为什么这会是我期望的行为[2, 3, 1, 4, 5]？

正如你可以看到的那样,这个重复的数字现象一次又一次地出现,直到阵列最终被反转.我错过了什么？它显然是在每个突变后的某个地方保留了数组的副本arr.

Answer 1

当数组是小型浏览器时（嗯......至少 chrome、safari 和 node）使用插入排序。您看到的行为是查看插入排序循环中间的数组的结果。您可以使用以下命令重现它：

let arr = [ 1, 2, 3, 4, 5];

function InsertionSort(a, comparefn) {
    let from = 0
    let to = a.length
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
        var order = comparefn(tmp, element); //<-- your console.log is peaking at the array here
        if (order > 0) {
          a[j + 1] = tmp;
        } else {
          break;
        }
      }
      a[j + 1] = element;
    }
  };

InsertionSort(arr,  (a,b) => {
    console.log(arr.join(","))
    return b-a
})
console.log(arr)

请记住，这不是必需的实现，因此您不必依赖此行为。