Javascript Array.sort() 方法在不同浏览器中的稳定性如何？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3026281/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the stability of the Array.sort() method in different browsers?
提问by Boushley
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.
我知道 ECMA Script 规范没有指定用于排序数组的算法，也没有指定排序是否应该稳定。
I've found this information for Firefoxwhich specifies that firefox uses a stable sort.
我找到了 Firefox 的这个信息，它指定 firefox 使用稳定的排序。
Does anyone know about IE 6/7/8, Chrome and Safari?
有人知道 IE 6/7/8、Chrome 和 Safari 吗？
采纳答案by Crescent Fresh
As of ES2019, sortis required to be stable. In ECMAScript 1st edition through ES2018, it was allowed to be unstable.
从 ES2019 开始，sort需要稳定。在 ECMAScript 第一版到 ES2018 中，它被允许不稳定。
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.
简单的测试用例（忽略标题，如果引擎的排序稳定，第二组数字应该是连续的）。注意：此测试用例不适用于某些版本的 Chrome（从技术上讲是 V8），这些版本根据数组的大小切换排序算法，对小数组使用稳定排序，对大数组使用不稳定排序。（详细信息。）请参阅问题末尾的修改版本，该版本使数组足够大以触发行为。
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
- Firefox < 3: unstable
- Firefox >= 3: stable
- Chrome < 70: unstable
- Chrome >= 70: stable
- Opera < 10: unstable
- Opera >= 10: stable
- Safari 4: stable
- Edge: unstable for long arrays (>512 elements)
- IE6+：稳定
- Firefox < 3：不稳定
- Firefox >= 3：稳定
- Chrome < 70：不稳定
- Chrome >= 70：稳定
- Opera < 10：不稳定
- Opera >= 10：稳定
- Safari 4：稳定
- 边缘：对于长数组（>512 个元素）不稳定
All tests on Windows.
Windows 上的所有测试。
See also:Fast stable sorting algorithm implementation in javascript
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:
这个测试用例（从这里修改）将通过确保数组有足够的条目来选择“更有效”的排序方法来演示 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");
}回答by Dummy00001
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 相比，仍然需要更多的额外内存。我想这就是为什么很少有规范要求稳定排序的原因。
回答by Mathias Bynens
As of V8 v7.0 and Chrome 70, our Array.prototype.sortimplementation is now stable.
从 V8 v7.0 和 Chrome 70 开始，我们的Array.prototype.sort实现现在是稳定的。
Previously, V8 used an unstable QuickSort for arrays with more than 10 elements. Now, V8 uses the stable TimSort algorithm.
以前，V8 对超过 10 个元素的数组使用不稳定的 QuickSort 。现在，V8 使用稳定的 TimSort 算法。
The only major engine JavaScript engine that still has an unstable Array#sortimplementation is Chakra, as used in Microsoft Edge. Chakra uses QuickSort for arrays with more than 512 elements. For smaller arrays, it uses a stable insertion sort implementation.
唯一仍然具有不稳定Array#sort实现的主要引擎 JavaScript 引擎是 Microsoft Edge 中使用的 Chakra。Chakra 对超过 512 个元素的数组使用 QuickSort 。对于较小的数组，它使用稳定的插入排序实现。
回答by unomi
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/提交补丁以将此类测试包含在其套件中。但同样，特征检测优于浏览器检测。
