Array.prototype.sort() 的排序稳定性
排序稳定性(stable sorting)是排序算法的重要属性,指的是排序关键字相同的项目,排序前后的顺序不变。
const arr = [
'peach',
'straw',
'apple',
'spork'
];
const stableSorting = (s1, s2) => {
if (s1[0] < s2[0]) return -1;
return 1;
};
arr.sort(stableSorting)
// ["apple", "peach", "straw", "spork"]
上面代码对数组arr
按照首字母进行排序。排序结果中,straw
在spork
的前面,跟原始顺序一致,所以排序算法stableSorting
是稳定排序。
const unstableSorting = (s1, s2) => {
if (s1[0] <= s2[0]) return -1;
return 1;
};
arr.sort(unstableSorting)
// ["apple", "peach", "spork", "straw"]
上面代码中,排序结果是spork
在straw
前面,跟原始顺序相反,所以排序算法unstableSorting
是不稳定的。
常见的排序算法之中,插入排序、合并排序、冒泡排序等都是稳定的,堆排序、快速排序等是不稳定的。不稳定排序的主要缺点是,多重排序时可能会产生问题。假设有一个姓和名的列表,要求按照“姓氏为主要关键字,名字为次要关键字”进行排序。开发者可能会先按名字排序,再按姓氏进行排序。如果排序算法是稳定的,这样就可以达到“先姓氏,后名字”的排序效果。如果是不稳定的,就不行。
早先的 ECMAScript 没有规定,Array.prototype.sort()
的默认排序算法是否稳定,留给浏览器自己决定,这导致某些实现是不稳定的。ES2019 明确规定,Array.prototype.sort()
的默认排序算法必须稳定。这个规定已经做到了,现在 JavaScript 各个主要实现的默认排序算法都是稳定的。