1. sort 方法的基本使用

sort 方法是對數(shù)組元素進(jìn)行排序散罕，默認(rèn)排序順序是先將元素轉(zhuǎn)換為字符串横腿，然后再進(jìn)行排序

arr.sort([compareFunction])

其中 compareFunction 用來指定按某種順序進(jìn)行排列的函數(shù)聊品，如果省略不寫，元素按照轉(zhuǎn)換為字符串的各個字符的 Unicode 位點(diǎn)進(jìn)行排序

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

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

從上面的執(zhí)行結(jié)果可以看出百新，如果不加參數(shù)檬贰，在第二段代碼中，21 會排到 4 的前面遵湖。這樣按照從小到大的邏輯是行不通的悔政，如果想要按照從小到大排序或者從大到小排序，那么上面的代碼就需要調(diào)整為下面這樣

const array1 = [1, 30, 4, 21, 100000];
array1.sort((a,b) => b - a);
console.log(array1); // [100000, 30, 21, 4, 1]

const array1 = [1, 30, 4, 21, 100000];
array1.sort((a,b) => a - b);
console.log(array1); // [1, 4, 21, 30, 100000]

如果指明了 compareFunction 參數(shù) 延旧，那么數(shù)組會按照調(diào)用該函數(shù)的返回值排序谋国，即 a 和 b 是兩個將要被比較的元素：

• 如果 compareFunction（a, b）小于 0，那么 a 會被排列到 b 之前
• 如果 compareFunction（a, b）等于 0迁沫，a 和 b 的相對位置不變
• 如果 compareFunction（a, b）大于 0芦瘾，b 會被排列到 a 之前

2. sort 方法的底層實現(xiàn)

下面的源碼均來自 V8 源碼中關(guān)于 sort 排序的摘要闷盔，地址：V8 源碼 sort 排序部分

如果要排序的元素個數(shù)是 n 的時候，那么就會有以下幾種情況：

1. 當(dāng) n<=10 時旅急，采用插入排序
2. 當(dāng) n>10 時，采用三路快速排序
3. 10<n <=1000牡整，采用中位數(shù)作為哨兵元素
4. n>1000藐吮，每隔 200~215 個元素挑出一個元素，放到一個新數(shù)組中逃贝，然后對它排序谣辞，找到中間位置的數(shù)，以此作為中位數(shù)

2.1 為什么元素個數(shù)少的時候要采用插入排序

雖然插入排序理論上是平均時間復(fù)雜度為 O(n^2) 的算法沐扳，快速排序是一個平均 O(nlogn) 級別的算法泥从。但是它們也有最好的時間復(fù)雜度情況，而插入排序在最好的情況下時間復(fù)雜度是 O(n)

在實際情況中兩者的算法復(fù)雜度前面都會有一個系數(shù)沪摄，當(dāng) n 足夠小的時候躯嫉，快速排序 nlogn 的優(yōu)勢會越來越小。倘若插入排序的 n 足夠小杨拐，那么就會超過快排祈餐。而事實上正是如此，插入排序經(jīng)過優(yōu)化以后哄陶，對于小數(shù)據(jù)集的排序會有非常優(yōu)越的性能帆阳，很多時候甚至?xí)^快排。因此屋吨，對于很小的數(shù)據(jù)量蜒谤，應(yīng)用插入排序是一個非常不錯的選擇

2.2 為什么要花這么大的力氣選擇哨兵元素？

因為快速排序的性能瓶頸在于遞歸的深度至扰，最壞的情況是每次的哨兵都是最小元素或者最大元素鳍徽，那么進(jìn)行 partition（一邊是小于哨兵的元素，另一邊是大于哨兵的元素）時渊胸，就會有一邊是空的旬盯。如果這么排下去，遞歸的層數(shù)就達(dá)到了 n , 而每一層的復(fù)雜度是 O(n)翎猛，因此快排這時候會退化成 O(n^2) 級別

因此讓哨兵元素盡可能地處于數(shù)組的中間位置胖翰，讓最大或者最小的情況盡可能少

官方實現(xiàn)的 sort 排序算法的代碼基本結(jié)構(gòu)

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) {
  // 比較函數(shù)未傳入
  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;
    }

  }

  // 元素個數(shù)大于1000時尋找哨兵元素
  function GetThirdIndex(a, from, to) {   
    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;
  }

  // 快速排序?qū)崿F(xiàn)
  function QuickSort(a, from, to) {  
    //哨兵位置
    var third_index = 0;

    while (true) {
      if (to - from <= 10) {
        InsertionSort(a, from, to); // 數(shù)據(jù)量小，使用插入排序切厘，速度較快
        return;
      }

      third_index = to - from > 1000
        ? GetThirdIndex(a, from, to)
        : from + ((to - from) >> 1); // 小于1000 直接取中點(diǎn)

      // 下面開始快排
      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++;
          }
        }
      }

      // 快排的核心思路萨咳，遞歸調(diào)用快速排序方法
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
    }
  }
}

3. 總結(jié)