前端 Array.sort() 源码学习

春光十里哥

源码地址

V8源码Array
710行开始为sort()相关
Array.sort()方法是那种排序呢？

去看源码主要是源于这个问题

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

复制代码

这块代码是对于非数组的一个处理
注释里面说到

1. // 通常使用快速排序算法
2. // 如果数组长度小于23，则插入排序效率更好

复制代码

返回的max会在下面用到
第五块代码

1. if (!IS_CALLABLE(comparefn)) {
2.   comparefn = function (x, y) {
3.     if (x === y) return 0;
4.     if (%_IsSmi(x) && %_IsSmi(y)) {
5.       return %SmiLexicographicCompare(x, y);
6.     }
7.     x = TO_STRING(x);
8.     y = TO_STRING(y);
9.     if (x == y) return 0;
10.     else return x < y ? -1 : 1;
11.   };
12. }

复制代码

注释翻译：

1. // Smi：小整数(Small integers)V8引擎中的元素类型之一
2. `https://medium.com/@justjavac/v8-internals-how-small-is-a-small-integer-ba5e17a3ae5f`
3. // PS: markdown语法有问题，这里直接贴出 url

复制代码

可能因为英语语法水平不够，单看注释还有点不明白
大致意思是，把“掀开的东西，再盖上”
直接看下面一块代码，看看这个shadow操作到底干了啥叭
第六块代码

[code]// Set a value of "undefined" on all indices in the range from..to// where a prototype of obj has an element. I.e., shadow all prototype// elements in that range.var ShadowPrototypeElements = function(obj, from, to) {  for (var proto = %object_get_prototype_of(obj); proto;        proto = %object_get_prototype_of(proto)) {        var indices = IS_PROXY(proto) ? to : %GetArrayKeys(proto, to);        if (IS_NUMBER(indices)) {          // It's an interval.          var proto_length = indices;          for (var i = from; i < proto_length; i++) {            if (HAS_OWN_PROPERTY(proto, i)) {              obj = UNDEFINED;            }          }        }         else {            for (var i = 0; i < indices.length; i++) {                var index = indices;                if (from