Array.prototype.sort() 的排序稳定性

排序稳定性(stable sorting)是排序算法的重要属性,指的是排序关键字相同的项目,排序前后的顺序不变。

  1. const arr = [
  2. 'peach',
  3. 'straw',
  4. 'apple',
  5. 'spork'
  6. ];
  7. const stableSorting = (s1, s2) => {
  8. if (s1[0] < s2[0]) return -1;
  9. return 1;
  10. };
  11. arr.sort(stableSorting)
  12. // ["apple", "peach", "straw", "spork"]

上面代码对数组arr按照首字母进行排序。排序结果中,strawspork的前面,跟原始顺序一致,所以排序算法stableSorting是稳定排序。

  1. const unstableSorting = (s1, s2) => {
  2. if (s1[0] <= s2[0]) return -1;
  3. return 1;
  4. };
  5. arr.sort(unstableSorting)
  6. // ["apple", "peach", "spork", "straw"]

上面代码中,排序结果是sporkstraw前面,跟原始顺序相反,所以排序算法unstableSorting是不稳定的。

常见的排序算法之中,插入排序、合并排序、冒泡排序等都是稳定的,堆排序、快速排序等是不稳定的。不稳定排序的主要缺点是,多重排序时可能会产生问题。假设有一个姓和名的列表,要求按照“姓氏为主要关键字,名字为次要关键字”进行排序。开发者可能会先按名字排序,再按姓氏进行排序。如果排序算法是稳定的,这样就可以达到“先姓氏,后名字”的排序效果。如果是不稳定的,就不行。

早先的 ECMAScript 没有规定,Array.prototype.sort()的默认排序算法是否稳定,留给浏览器自己决定,这导致某些实现是不稳定的。ES2019 明确规定,Array.prototype.sort()的默认排序算法必须稳定。这个规定已经做到了,现在 JavaScript 各个主要实现的默认排序算法都是稳定的。