sort() 方法对数组的元素做原地的排序, 并返回这个数组. 默认按照字符串的 Unicode 编码排序. sort 排序可能是不稳定的. 但其实 sort 方法可能并没有你想象的那么简单, 不信的话你耐心往下看看.

默认排序

sort 方法支持传入一个比较函数, 如果不传入则默认按照其字符串的 Unicode 编码排序, 因此默认情况下会出现以下情况.

1
2
[5, 1, 4, 11, 42].sort()
// [1, 11, 4, 42, 5]

解决方法就是:

1
2
[5, 1, 4, 11, 42].sort((pre, curr) => pre - curr)
// [1, 4, 5, 11, 42]

pre - curr 的值有三种情况

  • 小于 0 时, curr 排在 pre 后面
  • 大于 0 时, curr 排在 pre 前面
  • 等于 0 时, curr 和 pre 的位置不变

另外, 我们也可以对字符串进行排序:

1
2
['d', 'c', 'b', 'a'].sort()
// [a, b, c, d]

可能?是不稳定?

因为 ECMAScript 只是制定了 sort 这个方法, 但并没有给出具体的实现方式以及是否需要稳定的要求, sort 的实现就和其他大多数的方法一样由浏览器自行制定. 不同的浏览器或者同个浏览器不同版本上 sort 方法可能是稳定的, 也可能是不稳定的.

这里结合 V8 源码分析下这个 sort 方法的内部调优过程.

在 V8 中, 会通过以下函数方法进入 innerArraySort 中

1
2
3
4
5
6
7
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);
}

源码有点长, 可以自己看下 这里

注释已经点明了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 22) arrays, insertion sort is used for efficiency.
  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;
    };
  }
  ...
}

第一行注释表明这是一个原地排序, 第二行注释说明当数组长度小于 22 时(其实应该是 10 ?), 使用插入排序.

再看上面给出的条件语句, 则是判断有没有传入 comparefn , 如果未传入, 则这里会去获取每两个数的字符串的 Unicode 码进行比较, 按照其字符串的 Unicode 编码实现排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var QuickSort = function QuickSort(a, from, to) {
  var third_index = 0;
  while (true) {
    // Insertion sort is faster for short arrays.
    if (to - from <= 10) {
      InsertionSort(a, from, to);
      return;
    }
    if (to - from > 1000) {
      third_index = GetThirdIndex(a, from, to);
    } else {
      third_index = from + ((to - from) >> 1);
    }
    ...
  }
}

  • 当数组长度小于等于 10 时, 直接使用插入排序, 该算法算法复杂度为 O(n2) , 明显是不稳定的

  • 当数组长度大于 10 小于等于 1000 时, 获取 third_index 即中位数. 这里的方法有点屌

    1
    third_index = from + ((to - from) >> 1);

    其实就是 from + ( to - from ) / 2 , 以后别用 /2 了, 用 >>1 逼格才高

  • 当数组长度大于 1000 时, 通过 GetThirdIndex 方法获取 third_index

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    var GetThirdIndex = function(a, from, to) {
      var t_array = new InternalArray();
      // Use both 'from' and 'to' to determine the pivot candidates.
      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;
    }

    这个方法就要好好琢磨琢磨了.

    关于 var increment = 200 + ((to - from) & 15) , 这里拿 to 与 from 之差与 15 (2^4 -1) 相与, 为什么是这样写, 我也不太明白 ╮(╯▽╰)╭ , 但这个很明显就是得到一个划分范围.

    然后进行划分, t_array 是一个二维数组, 第一维是下标, 第二维是下标对应的数组 a 的值. 这里根据划分值 increment 得到 t_array 这个数组, 其实这个数组就是 a 的划分, 记录了每个划分的第一个数的下标值和数值. 接着这个 t_array 根据第二维即数值来对划分做排序, 然后取中间的划分的下标值

    接着的部分到 partition 前的代码, 其实就是做下图的处理

    split.png

    以上其实是一个快速排序的优化算法 – 三数取中( median-of-three )

    正如已知的，快速排序的阿克琉斯之踵在于，最差数组组合情况下会算法退化。

    快速排序的算法核心在于选择一个基准 (pivot)，将经过比较交换的数组按基准分解为两个数区进行后续递归。试想如果对一个已经有序的数组，每次选择基准元素时总是选择第一个或者最后一个元素，那么每次都会有一个数区是空的，递归的层数将达到 n，最后导致算法的时间复杂度退化为 O(n²)。因此 pivot 的选择非常重要。

    v8采用的是 三数取中(median-of-three) 的优化：除了头尾两个元素再额外选择一个元素参与基准元素的竞争。

    第三个元素的选取策略大致为：

    1. 当数组长度小于等于1000时，选择折半位置的元素作为目标元素。
    2. 当数组长度超过1000时，每隔200-215个(非固定，跟着数组长度而变化)左右选择一个元素来先确定一批候选元素。接着在这批候选元素中进行一次排序，将所得的中位值作为目标元素

    最后取三个元素的中位值作为 pivot。

其实 Chrome 的快速排序也是饱受争议, 因为在此之前 JavaScript 的 sort 实现都是稳定的, Firefox 中使用的是归并排序, 归并排序是稳定的. 但至今 Chrome 还是坚持不稳定的快速排序算法 O__O “…

后面就是快速排序的算法了. 快速排序大概的步骤就是遍历数组, 将基准值插入到正确的位置中去, 然后以该位置左右划分, 以此递归进行下去.

常见误用

虽然 Chrome 和 Firefox 的 sort 方法实现不同, 但其实并没有什么影响. 但仍然有不少人会发现在 Chrome 的排序结果是错的, Firefox 则是正常的. 我没有去看 Firefox 的实现, 但是我大概知道为什么他们会出错．

其实大部分人都错在了 Chrome 下的 compareFn 要求返回值有三种情况, 正, 负和0. 而不少人则是返回 true 或 false. 看看下面这段代码, 这里是快速排序才需要进入的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
  // v2 <= v0 <= v1.
  var tmp = v0;
  v0 = v2;
  v2 = v1;
  v1 = tmp;
} else {
  // v0 <= v1 && v0 < v2
  var c12 = comparefn(v1, v2);
  if (c12 > 0) {
    // v0 <= v2 < v1
    var tmp = v1;
    v1 = v2;
    v2 = tmp;
  }
}

在 JavaScript 中, false >=0 和 true >=0 都是成立的. 既然如此, 那么 c02 这里就永远取第一条了. sort 方法返回值分为三种, 大于0, 小于0, 等于0. 不要再返回 true 或返回 false 了. 之所以你返回 true 或 false 也可以运行起来那只是因为 JavaScript 隐性的类型转换以及运气好, 没碰到快排而已=.=

比如以下代码在 Chrome 中的执行结果, 由于 Node 也是使用 V8, 所以 Node 也会有同样的问题

1
2
3
4
5
6
7
var a = [15, 51, 24, 95, 26, 88, 6, 14, 18, 11]
a.sort((pre, curr) => pre > curr)
// [6, 11, 14, 15, 18, 24, 26, 51, 88, 95]
var a = [15, 51, 24, 95, 26, 88, 6, 14, 18, 11, 17]
a.sort((pre, curr) => pre > curr)
// [88, 15, 11, 14, 6, 17, 18, 24, 26, 51, 95]

现在就可以解释了, 在 Chrome 中, 小于等于 10 的时候是插入排序, 排序正常, 但大于 10 的时候, 是快速排序, 如果函数返回值只有 true 或 false 那么就不正常了. 由于 Firefox 使用归并排序, 所以 Firefox 没有这个问题.

sort 方法还有常见的一个误用就是用于随机排序.

1
[...].sort(() => Math.round(Math.random())-0.5)

这并不能做到完全随机, 首先各个浏览器的 sort 方法实现就不同, 并且也不能证明其能进行随机的排序.

真的要进行完全随机的排序的话, 还是得使用洗牌算法, 它是一种等概率随机的 In-place 排列算法. 具体的实现可以自己去网上搜下~

参考资料: