javascript - 为什么排序时数组中出现重复元素？

Question

我知道如何使用 Array.sort() 在 javascript 中对数组进行排序，但我不知道下面代码中每次迭代的实际情况。在这段代码中，在某些时候一些重复的元素开始出现在数组中。我在很多网站上搜索过这个谜团的解释，但我不明白为什么会这样。在 chrome 浏览器中运行此代码。我猜它在浏览器的 native 代码上运行。但我想知道这背后的逻辑。

我知道排序是根据正负值和零值返回，但为什么会出现重复元素？

var arr = [4, 3, 2, 1];
arr.sort(function(a, b) {
  document.getElementById("output").innerHTML += ("[" + arr + "] " + 'a = ' + a + ' b = ' + b + "<br>");
  return a - b;
});
document.getElementById("output").innerHTML += "[" + arr + "]";

<div id="output"></div>

Answer 1

简短的回答是:

对于任何在数组上运行的就地算法，都不能保证数组的中间值是有效的或完整的。 Chrome 选择实现其排序算法的方式存在中间步骤，其中数组具有重复的值并且不是原始数组的完整集合，但这是完全可以接受的，因为排序算法尚未完成。

TLDR 版本:

如果你想知道这背后的确切逻辑，你可以在这里查看 Chrome 使用的 V8 javascript 引擎的源代码 https://github.com/v8/v8/blob/master/src/js/array.js

特别是对于这种情况

For short (length <= 22) arrays, insertion sort is used for efficiency.

//This function was copied from the link above
function InsertionSort(a, from, to) {
  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); //This is where your comparison function is called
      if (order > 0) {
        a[j + 1] = tmp;
      } else {
        break;
      }
    }
    a[j + 1] = element;
  }
};

逐步执行到第一个副本...

第一次比较:比较前的数组[4,3,2,1]

i=1, j=0, tmp=a=4, element=b=3 ，order=1，arr[1]=tmp=a=4，arr[0]=element=b=3

第二次比较:比较前的数组[3,4,2,1]

i=2, j=1, tmp=a=4, element=b=2 , order=2, arr[2]=tmp=a=4

第三次比较:比较前的数组[3,4,4,1]

i=2, j=0, tmp=a=3, element=b=2 (这仍然在外层 for 循环的内存中)，order=1，arr[1]=tmp=a=3，arr[0]=元素=b=2

第四次比较:比较前的数组[2,3,4,1]...

从这里您可以看出为什么数组中的值会短暂重复，这是因为 for 循环在插入排序中的设置方式。它被设置为写入数组的次数最少，并且搜索值保存在内存中，因此数组的中间值不需要有效。