Array.sort() 方法在不同浏览器中的稳定性如何? [英] What is the stability of the Array.sort() method in different browsers?

问题描述

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

I know that the ECMA Script specification does not specify which algorithm to use for sorting arrays, nor does it specify whether the sort should be stable.

我找到了此信息适用于 Firefox 指定 firefox 使用稳定排序.

I've found this information for Firefox which specifies that firefox uses a stable sort.

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

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

推荐答案

截至 ES2019，sort 需要稳定.在 ECMAScript 1st edition 到 ES2018 中，它被允许不稳定.

As of ES2019, sort is required to be stable. In ECMAScript 1st edition through ES2018, it was allowed to be unstable.

简单测试用例(忽略标题，第二组数字如果引擎的排序稳定，则应该是连续的).注意:此测试用例不适用于某些版本的 Chrome(从技术上讲是 V8)，这些版本根据数组的大小切换排序算法，对小数组使用稳定排序，对大数组使用不稳定排序.(详细信息.)请参阅问题末尾的修改使数组足够大以触发行为的版本.

Simple test case (ignore the heading, second set of numbers should be sequential if the engine's sort is stable). Note: This test case doesn't work for some versions of Chrome (technically, of V8) that switched sorting algorithms based on the size of the array, using a stable sort for small arrays but an unstable one for larger arrays. (Details.) See the end of the question for a modified version that makes the array large enough to trigger the behavior.

IE 的排序在我使用过它时就一直很稳定(IE6 也是如此).在 IE8 中再次检查，似乎仍然如此.

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 之前，情况并非总是如此.

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.

一些粗略的结果:

• IE6+:稳定
• 火狐3:不稳定
• Firefox >= 3:稳定
• 铬 <70:不稳定
• Chrome >= 70:稳定
• 歌剧
• 10:不稳定
• Opera >= 10:稳定
• Safari 4:稳定
• Edge:对于长数组不稳定(>512 个元素)

Windows 上的所有测试.

All tests on Windows.

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

此测试用例(从此处修改)将演示问题在 V8(例如，Node v6，Chrome

This test case (modified from here) will demonstrate the problem in V8 (for instance, Node v6, Chrome < v70) by ensuring the array has enough entries to pick the "more efficient" sort method; this is written with very old JavaScript engines in mind, so without modern features:

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");
}

这篇关于Array.sort() 方法在不同浏览器中的稳定性如何?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！