ichuan.net

自信打不死的心态活到老

javascript 数组的稳定性排序

javascrpt 数组的排序

Array.sort 是 javascript 数组的排序方法,默认按字串形式排序,可以传入一个自定义的排序函数 function (a, b) {},按返回值决定元素排序后的位置。

enter image description here

稳定性排序

指的是当数组里两个元素相同时,排序后它们的相对位置不应该发生改变。以上面的图片为例,数组有两个 3,假如排序后两个 3 的位置发生了调换,这个排序方法就是不稳定的。

ECMAScript 规范里有这么一句:

The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order)

也就是规范并没有规定各个实现者要实现稳定的排序,这就导致了一些问题。有人做过测试,得出了 Array.sort 在各浏览器中的稳定性列表:

enter image description here

很惊讶地发现 IE6 都可以达到稳定性排序,而最新版本的 Chrome 中竟然还是不稳定排序

Chrome 中重现

今天很偶然的遇到了 Chorme 中不稳定排序的 bug(需要浏览器环境,可在 Chrome Console 中执行):

enter image description here

在排序中我使用了返回值 0,即表示两个元素相等。期待的结果应该是 y 数组各元素位置不变,但明显第一个元素的就发生了变化。

解决方法

解决方式是换个排序方法,不用 Chrome 原生的 Array.sort。网上普遍使用一个 merge sort 作为替代。算法一直都是我的痛点,我想换个更简单点的解决思路。既然不稳定排序只发生在两个元素相等时,那如果我们记录每个元素原先的位置,在两个元素相等时利用原先位置做比较,不就是修复了这个 bug 了么?于是有了以下自定义的 Array.stableSort 方法:

Array.prototype.stableSort = function (fn) {
  if (!fn) {
    // 默认排序还按原生的
    return this.sort();
  }
  // 用新数组记录位置
  var newArr = this.map(function (i, j) { return {i:i, j:j}; });
  return newArr.sort(function (a, b) {
    result = fn(a.i, b.i);
    if (result === 0) {
      // 按原先元素位置排序
      return a.j - b.j;
    }
    return result;
  }).map(function (i) { return i.i; });
};

再来看下效果:

enter image description here

实现稳定排序了。至于为什么那个 DOM 结构的数组会触发这个 bug,暂时还是未知。

参考链接

  • https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
  • http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.4.11
  • http://stackoverflow.com/a/3027715/265989
  • https://code.google.com/p/v8/issues/detail?id=90
  • http://stackoverflow.com/questions/1427608/fast-stable-sorting-algorithm-implementation-in-javascript

Comments