Array.sort()方法在不同浏览器中的稳定性是什么？

Question

我知道ECMA脚本规范没有指定用于排序数组的算法,也没有指定排序是否应该是稳定的.

我在Firefox中找到了这个信息,它指明firefox使用稳定的排序.

有谁知道IE 6/7/8,Chrome和Safari？

Answer 1

Simple test case (ignore the heading, second set of numbers should be sequential if the engine's sort is stable).

IE's sort has been stable as long as I've ever used it (so IE6). Checking again in IE8 and it appears to still be the case.

虽然你链接到的Mozilla页面说Firefox的排序是稳定的,但我肯定地说在Firefox 2.0之前(包括)并不总是如此.

一些粗略的结果:

• IE6 +:稳定
• Firefox <3:不稳定
• Firefox> = 3:稳定
• Chrome <70:不稳定
• Chrome> = 70:稳定
• 歌剧<10:不稳定
• Opera> = 10:稳定
• Safari 4:稳定
• 边缘:对于长阵列不稳定

Windows上的所有测试.

另请参见: javascript中的快速稳定排序算法实现

Answer 2

我想分享我在C/C++中经常使用的技巧qsort().

JS的sort()允许指定比较函数.创建相同长度的第二个数组,并用0增加的数字填充它.

function stableSorted(array, compareFunction) {
  compareFunction = compareFunction || defaultCompare;
  var indicies = new Array(array.length);
  for (var i = 0; i < indicies.length; i++)
    indicies[i] = i;

这是原始数组的索引.我们要对第二个数组进行排序.制作自定义比较功能.

  indicies.sort(function(a, b)) {

它将从第二个数组中获取两个元素:将它们用作原始数组的索引并比较元素.

    var aValue = array[a], bValue = array[b];
    var order = compareFunction(a, b);
    if (order != 0)
      return order;

如果元素恰好相等,那么比较它们的索引以使订单稳定.

   if (a < b)
     return -1;
   else
     return 1;
  });

在sort()之后,第二个数组将包含索引,您可以使用这些索引以稳定的排序顺序访问原始数组的元素.

  var sorted = new Array(array.length);
  for (var i = 0; i < sorted.length; i++)
    sorted[i] = array[indicies[i]];
  return sorted;
}

// The default comparison logic used by Array.sort(), if compareFunction is not provided:
function defaultCompare(a, b) {
  a = String(a);
  b = String(b);
  if (a < b) return -1;
  else if (a > b) return 1;
  else return 0;
}

一般来说,稳定的排序算法只会越来越成熟,并且与优质的qsort相比仍然需要更多的额外内存.我猜这就是为什么很少有规格要求稳定排序的原因.

Answer 3

从V8 v7.0和Chrome 70开始，我们的Array.prototype.sort实施现已稳定。

以前，V8对具有10个以上元素的数组使用不稳定的QuickSort 。现在，V8使用稳定的TimSort算法。

唯一仍具有不稳定Array#sort实现的主要JavaScript引擎是Chakra，如Microsoft Edge中所使用的。Chakra将QuickSort用于具有512个以上元素的数组。对于较小的数组，它使用稳定的插入排序实现。

演示： https : //mathiasbynens.be/demo/sort-stability