我知道 ECMA Script 规范没有指定用于排序数组的算法，也没有指定排序是否应该稳定。
我找到了 Firefox 的此信息，它指定 firefox 使用稳定的排序。
有人知道 IE 6/7/8、Chrome 和 Safari 吗？
Array.sort() 方法在不同浏览器中的稳定性如何？
IT技术
javascript
arrays
sorting
cross-browser
stable-sort
2021-02-02 13:32:24
5个回答
从 ES2019 开始，sort需要稳定。在 ECMAScript 第一版到 ES2018 中，它被允许不稳定。
简单的测试用例（忽略标题，如果引擎的排序稳定，第二组数字应该是连续的）。注意：此测试用例不适用于某些版本的 Chrome（从技术上讲是 V8），这些版本根据数组的大小切换排序算法，对小数组使用稳定排序，对大数组使用不稳定排序。（详细信息。）请参阅问题末尾的修改版本，该版本使数组足够大以触发行为。
只要我用过它（IE6 也是如此），IE 的排序就一直很稳定。在 IE8 中再次检查，似乎仍然如此。
尽管您链接到的 Mozilla 页面说 Firefox 的排序是稳定的，但我肯定地说，在（包括）Firefox 2.0 之前，情况并非总是如此。
一些粗略的结果：
- IE6+：稳定
- Firefox < 3：不稳定
- Firefox >= 3：稳定
- Chrome < 70：不稳定
- Chrome >= 70：稳定
- Opera < 10：不稳定
- Opera >= 10：稳定
- Safari 4：稳定
- 边缘：对于长数组（>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");
}我想分享一个我经常在 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 相比，仍然需要更多的额外内存。我想这就是为什么很少有规范要求稳定排序的原因。
从 V8 v7.0 和 Chrome 70 开始，我们的Array.prototype.sort实现现在是稳定的。🎉
以前，V8 对超过 10 个元素的数组使用不稳定的 QuickSort 。现在，V8 使用稳定的 TimSort 算法。
唯一仍然具有不稳定Array#sort实现的主要引擎 JavaScript 引擎是 Microsoft Edge 中使用的 Chakra。Chakra 对超过 512 个元素的数组使用 QuickSort 。对于较小的数组，它使用稳定的插入排序实现。
如果有人觉得它有用，我有一个 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;
}
});
}如果您正在寻找应该使用非本机排序算法的浏览器列表，我的建议是不要。
而是在脚本加载时进行排序健全性检查并从中做出决定。
由于规范在这方面不需要特定的行为，因此即使在同一浏览器行中，也不能免于以后的更改。
您可以向http://www.browserscope.org/提交补丁以将此类测试包含在其套件中。但同样，特征检测优于浏览器检测。
其它你可能感兴趣的问题