Array.prototype.sort & 排序

[yaofly2012]

Array.prototype.sort深挖的内容比较多。

一、语法

1. 会改变数组本身；
2. 默认会把元素（即使是数字）转成字符串，再按照字符串的每个字符UTF-16码点值的升序排列；

var array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1); // [1, 100000, 21, 30, 4]

3. 字符串比较的是UTF-16码点值（详细参考String），对于非BMP字符如果按照Unicode码点值排序需要提供compareFn实参。

["你", 'Ｚ'].sort(); // ["你", "Ｚ"]
["你", 'Ｚ'].sort((a, b) => a.codePointAt(0) - b.codePointAt(0)) //  ["Ｚ", "你"]

二、采用什么算法？

2.1 现状

1. 规范里并没要求具体采用什么排序算法；
2. 甚至还没要求排序算法是否稳定。

这导致各个浏览器实现不一致，甚至不同版本的浏览器也不一样。

Chrome比较折腾

1. 曾经是插入排序+快速排序

// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.

2. v6.9也是[插入排序+快速排序]，不过稍微不同

// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.

3. 从V8 v7.0 / Chrome 70采用TimSort。

为啥这么折腾呢？

describes our journey to move V8 to a stable algorithm and make performance more predictable.

2.2 未来

1. ES2019开始规定sort方法必须采用稳定的排序算法。
   让排序结果可预期。
2. 但依旧不限制具体的排序算法。
   目前还没万能的方式，看各位取舍了。

各浏览器也都基本采用了稳定排序算法：

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)

参考

1. MDN sort
2. Getting things sorted in V8
3. JavaScript Array.sort() 运行与V8源码运行有差异？
4. Javascript Array.sort implementation?
5. What is the stability of the Array.sort() method in different browsers?
6. Stable Array.prototype.sort
7. What is Array.prototype.sort() time complexity?
8. Merge sort, JavaScript and ECMAScript 2015 (ES6)

[yaofly2012]

排序算法

一、概念

排序算法处理考虑时间复杂度，空间复杂度还需要考虑稳定性。

1. 时间复杂度；
2. 空间复杂度；
3. 稳定性。

稳定性

排序算法稳定性的简单形式化定义为：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。
通俗地讲就是保证排序前后两个相等的数的相对顺序不变。

排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位排序后元素的顺序在高位也相同时是不会改变的。

浏览器实现的差异

1. 从各浏览器厂商的实现看出目前排序算法没有最好的，要不然也不至于采用的算法不一致；
2. 从Chrome的迭代情况看出排序算法的选择应该针对特定的情况有选择更合适的算法。

逐步统一：

1. 如上，基本都采用稳定的算法.

二、实现

摘自Is there an ideal comparison sort?

参考

1. 常用排序算法总结(一)
2. Is there an ideal comparison sort?