Array.sort()方法在不同浏览器中的稳定性如何？
我知道ECMA脚本规范没有指定用于数组排序的算法，也没有指定排序是否应该是稳定的。
我找到了this information for Firefox，它指定火狐使用稳定的排序。
有人知道IE 6/7/8，Chrome和Safari吗？
回答 5
Stack Overflow用户
发布于 2010-06-12 14:14:52
从ES2019开始，要求sort是稳定的。在通过ES2018的ECMAScript第一版中，它被允许是不稳定的。
Simple test case (忽略标题，如果引擎的排序是稳定的，第二组数字应该是连续的)。注意:这个测试用例不适用于一些版本的Chrome (严格来说，是V8)，它们根据数组的大小切换排序算法，对小数组使用稳定的排序，而对较大的数组使用不稳定的排序。(Details.)请参见问题末尾的修改版本，该版本使数组足够大，以触发行为。
IE的排序自从我使用它以来一直是稳定的(所以IE6)。再次检查IE8，它似乎仍然是这种情况。
尽管你链接到的Mozilla页面说Firefox的排序是稳定的，但我肯定地说，在Firefox2.0之前(包括)，情况并不总是这样。
一些粗略的结果：
不稳定阵列：stable
- Firefox < 3: unstable
- Firefox阵列3：stable
- Chrome < 70: unstable
- Chrome阵列70：stable
- Opera < 10: unstable
- Opera阵列10：stable
- Safari 4：stable
- Edge：(>512 elements)
>=
Windows上的所有测试。
另请参阅： Fast stable sorting algorithm implementation in javascript
这个测试用例(从here修改而来)将通过确保数组有足够的条目来选择“更有效”的排序方法来演示V8 (例如，节点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");
}
Stack Overflow用户
发布于 2010-06-12 07:10:19
我想分享我在qsort()的C/C++中经常使用的一个技巧。
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相比，仍然需要更多的额外内存。我想这就是为什么很少有规范要求稳定排序的原因。
Stack Overflow用户
发布于 2018-09-03 22:40:38
从V8 v7.0和Chrome70开始，我们的Array.prototype.sort实现现在是稳定的。
以前，V8对带有more than 10 elements的数组使用不稳定的QuickSort。现在，V8使用稳定的TimSort算法。
唯一一个仍然有不稳定Array#sort实现的主要引擎JavaScript引擎是Chakra，就像Microsoft Edge中使用的那样。Chakra对带有more than 512 elements的数组使用QuickSort。对于较小的数组，它使用稳定的插入排序实现。
https://stackoverflow.com/questions/3026281
复制相似问题
腾讯云开发者
