数组中。在不同的浏览器中排序稳定性。

What is the stability of Array.sort in different browsers. I know that the ECMA Script specification does not specify which algorithm to use, nor does it specify whether the sort should be stable.

什么是数组的稳定性。在不同的浏览器。我知道ECMA脚本规范没有指定使用哪种算法，也没有指定排序是否应该稳定。

I've found this information for Firefox at https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort which specifies that firefox uses a stable sort.

我在https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort上找到了Firefox的这些信息，这些信息指定Firefox使用稳定的排序。

Does anyone know about IE 6/7/8, Chrome, Safari?

有人知道IE 6/7/8, Chrome, Safari吗?

3 个解决方案

#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.

IE的排序自我使用以来就一直稳定(IE6)。再次在IE8中进行检查，似乎仍然如此。

And although that Mozilla page you link to says Firefox's sort is stable, I definitely say this was not always the case prior to (and including) Firefox 2.0.

尽管你链接到的Mozilla页面说Firefox的排序是稳定的，但我肯定地说，在Firefox 2.0之前(包括)，情况并不总是如此。

Some cursory results:

一些粗略的结果:

IE6+: stable
IE6 +:稳定
Firefox < 3: unstable
Firefox < 3:不稳定
Firefox >= 3: stable
Firefox > = 3:稳定
Chrome <= 5 (i.e., all versions to date): unstable
Chrome < = 5(即。):不稳定
Opera < 10: unstable
歌剧< 10:不稳定
Opera >= 10: stable
歌剧> = 10:稳定
Safari 4: stable
Safari 4:稳定

All tests on Windows.

在Windows上所有的测试。

#2

I'd like to share a trick I routinely use in C/C++ for qsort().

我想分享一个在C/ c++中用于qsort()的技巧。

JS' sort() allows to specify a compare function. Create second array of the same length and fill it with increasing numbers from 0.

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;

This are indexes into the original array. We are going to sort the second array. Make a custom compare function.

这是原始数组中的索引。我们要对第二个数组排序。做一个自定义比较函数。

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

It will get the two elements from the second array: use them as indexes into the original arrays and compare the elements.

它将从第二个数组中获得这两个元素:将它们作为索引使用到原始数组中，并对元素进行比较。

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

If elements happen to be equal, then compare their indexes to make the order stable.

如果元素碰巧相等，那么比较它们的索引，使顺序稳定。

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

After the sort(), the second array would contain indexes which you can use to access the elements of original array in stable sorted order.

在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;
}

In general, stable sort algorithms are only maturing and still require more extra memory compared to the good ol' qsort. I guess that's why very few specs mandate stable sort.

一般来说，稳定的排序算法只在成熟阶段，与好的ol' qsort相比，仍然需要更多的内存。我想这就是为什么很少的规格要求稳定的类型。

#3

-2

If you are looking for a list of browsers where you should utilize a non native sorting algorithm, my suggestion is don't.

如果您正在寻找一个应该使用非本地排序算法的浏览器列表，我的建议是不要使用。

Instead do a sort sanity check when the script loads and make your decision from that.

相反，在脚本加载时进行排序完整性检查，并据此做出决定。

As the spec doesn't require a particular behavior in that regard, it is not immune to later change, even within the same browser line.

由于该规范在这方面不需要特定的行为，因此即使在相同的浏览器行中，它也不能避免以后的更改。

You could submit a patch to http://www.browserscope.org/ to include such tests in their suite. But again, feature detection is superior to browser detection.

您可以向http://www.browserscope.org/提交一个补丁，将这样的测试包含在他们的套件中。但再次强调，功能检测优于浏览器检测。

#1