Array.Sort()方法在不同浏览器中的稳定性如何？

Question

Array.Sort()方法在不同浏览器中的稳定性如何？我知道ECMA脚本规范没有指定用于排序数组的算法，也没有指定排序是否应该稳定。我发现这是Firefox的信息它指定Firefox使用稳定的排序。有人知道IE6/7/8，Chrome和Safari吗？

Answer 1

我想分享一个我在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;}

一般来说，稳定的排序算法仅仅是成熟的，与好的ol‘qSort相比，仍然需要更多的额外内存。我想这就是为什么很少有规格要求稳定排序。