解析

Array.prototype.sort()

sort() 方法用于对数组的元素进行排序，并返回数组。
如果省略，sort方法会调用数组中每一项的toString()方法，然后按照unicode编码进行排序，如果数组含有undefined元素，它们将会被排到尾部。

const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// expected output: Array ["Dec", "Feb", "Jan", "March"]

var arr=[3,24,6,18,7,21];
arr.sort();
console.log(arr); //=>[18,21,24,3,6,7]

1
2
3
4
5
6
7
8
9

数组元素超过2位数排序就出了问题，上面已经说过了sort排序是按照元素的unicode码来进行排序了，先对每一项的第一位按照ascii从小到大进行排序，如果第一位相同再将第二位按照unicode从小到大进行排序。因为 1、2、3、6、7的unicode码分别是：31、32、33、36、37，所以顺序首先是：[18,14,3,6,7,21]的第一位ascii码相同，所以再比较第二位，4的ascii码是34，所以21在24的前面，最终的排序结果是：[18,21,24,3,6,7]。虽然原因找到了，但是不是我们想要的排序结果，Array.sort()方法允许我们传入一个比较函数进去。

排序

升序排列 : return a - b
降序排序 : return a - b

sort源码分析

查阅 v8源码sort部分 我们可以发现，对于需要排序的元素个数n，具体排序策略有几下中情形：

当 n<=10 时，采用插入排序；
当 n>10 时，采用三路快速排序；
10<n <=1000，采用中位数作为哨兵元素；
n>1000，每隔 200~215 个元素挑出一个元素，放到一个新数组中，然后对它排序，找到中间位置的数，以此作为中位数。
乍一看结论你可能会纠结两个问题

1、为何元素较少的时候要用快排
其实仔细分析一下不难究其原因。对于插排和快排，理论上的平均时间复杂度分别为O(n^2)和O(nlogn)，其中插排在最好情况下的时间复杂度是 O(n)。对比不难得出结论，当n足够小的时候，快排优势变小。事实上插排经优化后对于小数据集的排序性能可以超过快排。

2、为何要选择哨兵元素
因为快速排序的性能瓶颈在于递归的深度，最坏的情况是每次的哨兵都是最小元素或者最大元素，那么进行 partition（一边是小于哨兵的元素，另一边是大于哨兵的元素）时，就会有一边是空的。如果这么排下去，递归的层数就达到了n, 而每一层的复杂度是 O(n)，因此快排这时候会退化成O(n^2)级别。

这种情况是要尽力避免的，那么如何来避免？就是让哨兵元素尽可能地处于数组的中间位置，让最大或者最小的情况尽可能少

最后我们看下源码中的sort的基本结构

function ArraySort(comparefn) {
    CHECK_OBJECT_COERCIBLE(this,"Array.prototype.sort");
    var array = TO_OBJECT(this);
    var length = TO_LENGTH(array.length);
    return InnerArraySort(array, length, comparefn);
}
function InnerArraySort(array, length, comparefn) {
// 比较函数未传入
if (!IS_CALLABLE(comparefn)) {
      comparefn = function (x, y) {
        if (x === y) return 0;
        if (%_IsSmi(x) && %_IsSmi(y)) {
          return %SmiLexicographicCompare(x, y);
        }
        x = TO_STRING(x);
        y = TO_STRING(y);
        if (x == y) return 0;
        else return x < y ? -1 : 1;
   };
}
function InsertionSort(a, from, to) {
  // 插入排序
  for (var i = from + 1; i < to; i++) {
        var element = a[i];
        for (var j = i - 1; j >= from; j--) {
          var tmp = a[j];
          var order = comparefn(tmp, element);
          if (order > 0) {
            a[j + 1] = tmp;
          } else {
            break;
          }
        }
      a[j + 1] = element;
   }
}
function GetThirdIndex(a, from, to) {   // 元素个数大于1000时寻找哨兵元素
  var t_array = new InternalArray();
  var increment = 200 + ((to - from) & 15);
  var j = 0;
  from += 1;
  to -= 1;
  for (var i = from; i < to; i += increment) {
     t_array[j] = [i, a[i]];
     j++;
  }
  t_array.sort(function(a, b) {
     return comparefn(a[1], b[1]);
  });
  var third_index = t_array[t_array.length >> 1][0];
  return third_index;
}
function QuickSort(a, from, to) {  // 快速排序实现
      //哨兵位置
      var third_index = 0;
      while (true) {
        if (to - from <= 10) {
          InsertionSort(a, from, to); // 数据量小，使用插入排序，速度较快
          return;
        }
        if (to - from > 1000) {
          third_index = GetThirdIndex(a, from, to);
        } else {
          // 小于1000 直接取中点
          third_index = from + ((to - from) >> 1);
        }
        // 下面开始快排
        var v0 = a[from];
        var v1 = a[to - 1];
        var v2 = a[third_index];
        var c01 = comparefn(v0, v1);
        if (c01 > 0) {
          var tmp = v0;
          v0 = v1;
          v1 = tmp;
        }
        var c02 = comparefn(v0, v2);
        if (c02 >= 0) {
          var tmp = v0;
          v0 = v2;
          v2 = v1;
          v1 = tmp;
        } else {
          var c12 = comparefn(v1, v2);
          if (c12 > 0) {
            var tmp = v1;
            v1 = v2;
            v2 = tmp;
          }
        }
        a[from] = v0;
        a[to - 1] = v2;
        var pivot = v1;
        var low_end = from + 1; 
        var high_start = to - 1;
        a[third_index] = a[low_end];
        a[low_end] = pivot;
        partition: for (var i = low_end + 1; i < high_start; i++) {
          var element = a[i];
          var order = comparefn(element, pivot);
          if (order < 0) {
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
          } else if (order > 0) {
            do {
              high_start--;
              if (high_start == i) break partition;
              var top_elem = a[high_start];
              order = comparefn(top_elem, pivot);
            } while (order > 0);
            a[i] = a[high_start];
            a[high_start] = element;
            if (order < 0) {
              element = a[i];
              a[i] = a[low_end];
              a[low_end] = element;
              low_end++;
            }
          }
        }
        // 快排的核心思路，递归调用快速排序方法
        if (to - high_start < low_end - from) {
          QuickSort(a, high_start, to);
          to = low_end;
        } else {
          QuickSort(a, from, low_end);
          from = high_start;
        }
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131