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

Question

我知道ECMA Script规范并没有指定用于排序数组的算法，也没有指定排序是否应该稳定。

我在这个火狐官方文档中找到了相关信息，说明火狐浏览器使用稳定排序。

有人了解IE 6/7/8、Chrome和Safari的情况吗？

- Boushley

Answer 1

从ES2019开始，sort被要求是稳定的。在ECMAScript 1版到ES2018期间，它可以是不稳定的。

简单测试案例（忽略标题，如果引擎的排序是稳定的，则第二组数字应为顺序）。注意：这个测试用例在某些Chrome版本（技术上说是V8）上不起作用，因为它们基于数组大小切换排序算法，对小型数组使用稳定排序，但对大型数组使用不稳定排序。（细节）请参见问题结尾的修改版本，使数组足够大以触发行为。

IE的排序方法在我使用IE6期间就已经是稳定的了。再次检查IE8，似乎仍然是这种情况。

虽然你链接的那个Mozilla页面说Firefox的排序方法是稳定的，但我肯定在Firefox 2.0之前（包括Firefox 2.0）这并不总是正确的。

一些初步结果：

• IE6+：稳定
• Firefox < 3：不稳定
• Firefox >= 3：稳定
• Chrome < 70：不稳定
• Chrome >= 70：稳定
• Opera < 10：不稳定
• Opera >= 10：稳定
• Safari 4：稳定
• Edge：长数组（>512个元素）不稳定

所有测试均在Windows上进行。

另请参阅： 在JavaScript中实现快速稳定的排序算法

该测试案例（从这里修改而来）将通过确保数组具有足够的条目选择“更有效”的排序方法来演示V8的问题（例如，Node v6、Chrome < v70），这是针对非常旧的JavaScript引擎编写的，因此没有现代功能：

function Pair(_x, _y) {
    this.x = _x;
    this.y = _y;
}
function pairSort(a, b) {
    return a.x - b.x;
}
var y = 0;
var check = [];
while (check.length < 100) {
    check.push(new Pair(Math.floor(Math.random() * 3) + 1, ++y));
}
check.sort(pairSort);
var min = {};
var issues = 0;
for (var i = 0; i < check.length; ++i) {
    var entry = check[i];
    var found = min[entry.x];
    if (found) {
        if (found.y > entry.y) {
            console.log("Unstable at " + found.i + ": " + found.y + " > " + entry.y);
            ++issues;
        }
    } else {
        min[entry.x] = {x: entry.x, y: entry.y, i: i};
    }
}
if (!issues) {
    console.log("Sort appears to be stable");
}

- Crescent Fresh

---

http://ofb.net/~sethml/is-sort-stable.html？（我为此保存了Web存档，以防万一） - Pierre

从IE9开始，IE的排序不再稳定。Chrome对于小于10个元素的数组是稳定的（这是使用插入排序作为其快速排序的基本情况的副作用）。 - James Montagne

@JamesMontagne：是的，Pierre的链接证实了。 - Crescent Fresh

Node.js / V8 继承了 Chrome 不稳定的实现。 - mnagel

Chrome自v70版本开始具有稳定的排序功能，Node.js自v11版本开始也支持。 - red-X

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相比需要更多的额外内存。我猜这就是为什么很少有规范强制要求使用稳定排序的原因。

- Dummy00001

Answer 3

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

以前，V8 对于具有 10 个以上元素的数组 使用不稳定的快速排序算法。现在，V8 使用了稳定的 TimSort 算法。

唯一还有不稳定 Array#sort 实现的主流 JavaScript 引擎是 Chakra，它在 Microsoft Edge 中使用。对于具有 512 个以上元素的数组，Chakra 使用快速排序算法。对于较小的数组，则使用稳定的插入排序实现。

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

- Mathias Bynens

---

你能简要解释一下为什么使用 QuickSort 的旧版 V8 实现被认为不稳定吗？无论如何，祝贺你的出色工作。 - Mathiasfc

快速排序通常不稳定，因为分区的方式。存在稳定的快速排序版本，但它们需要额外的内存并且效率不高。 - Mathias Bynens

它们应该在未来都保证稳定：https://github.com/tc39/ecma262/pull/1340 编辑：哈哈，好的，那个PR实际上是你自己的。^^' - lapo

Answer 4

如果有人觉得有用的话，我之前写了一个polyfill，现在已经移除了：

const stable = (count => {
    const
        array = new Array(count),
        buckets = {};

    let i, k, v;

    for (i = 0; i < count; ++i) {
        array[i] = [Math.floor(Math.random() * 3) + 1, i + 1];  // [1..3, 1..count]
    }

    array.sort((a, b) => a[0] - b[0]);

    for (i = 0; i < count; ++i) {
        [k, v] = array[i];

        if (buckets[k] > v) {
            return false;
        }

        buckets[k] = v;
    }

    return true;
// Edge's JS engine has a threshold of 512 before it goes unstable, so use a number beyond that:
})(600);

if (!stable) {
    const
        { prototype } = Array,
        { sort } = prototype;

    Object.defineProperty(prototype, 'sort', {
        configurable : true,

        value(sortFn) {
            const
                array = this,
                len = array.length,
                temp = new Array(len);

            let i;

            for (i = len; i-- > 0; /* empty */) {
                temp[i] = i;
            }

            sortFn = sortFn || defaultSort;

            sort.call(temp, (index1, index2) => sortFn(array[index1], array[index2]) || index1 - index2);

            // we cannot do this directly into array since we may overwrite an element before putting it into the
            // correct spot:
            for (i = len; i-- > 0; /* empty */) {
                temp[i] = array[temp[i]];
            }

            for (i = len; i-- > 0; /* empty */) {
                array[i] = temp[i];
            }

            return array;
        }
    });
}

- dongryphon

Answer 5

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

相反，在脚本加载时进行排序检查，并从中做出决定。

由于规范在这方面并没有要求特定的行为，因此即使在同一浏览器线路内，它也不免受到后来的更改的影响。

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

- unomi

---

我不确定你是否能够编写一个确保稳定排序的合理性检查。它可能一开始看起来很稳定，但下一刻可能就不稳定了。例如，如果排序某种方式依赖于 JavaScript 对象在内存中的位置 - 这是不可预测的事情，那么就可能发生这种情况。 - Rich Dougherty

@RichDougherty -- 我相信你是无法的。你不能通过运行它来证明一个排序算法是稳定的！这就像试图通过开一圈车来证明一辆汽车是可靠的。你必须分析算法和实现。 - Michael Lorton

@Malvolio，我认为我们是同意的。我的意思是，如果一个测试现在通过了，那么它肯定不能保证在未来也能通过，因此进行负载时间检查以确保稳定性是徒劳无功的。 - Rich Dougherty

@RichDougherty -- 重新阅读您的评论，我现在意识到，“不确定”是一种虚言。 - Michael Lorton

虽然从理论上讲你是正确的，但实际上很容易生成一个数据集和排序函数，如果稳定排序，则非常有可能使排序算法稳定，特别是对于较大的数据集。当然，证明排序不稳定也很容易。这里是我创建的一个示例：https://jsfiddle.net/1o5qgfzt/ 结果在控制台中显示。在Chrome中，长度最多为10的数组可以稳定排序，而超过10则不稳定。 - undefined