Array.sort()方法在不同浏览器中的稳定性如何？
Array.sort()方法在不同浏览器中的稳定性如何？
提问于 2010-06-12 05:10:38
我知道ECMA脚本规范没有指定用于数组排序的算法，也没有指定排序是否应该是稳定的。
我找到了this information for Firefox，它指定火狐使用稳定的排序。
有人知道IE 6/7/8，Chrome和Safari吗？
回答 2
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用户
发布于 2021-01-05 22:05:33
如果有人觉得它有用，我有一个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;
}
});
}
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3026281
复制相关文章
相似问题