稳定排序

发表于

算法中有许多排序算法，它们有的是稳定的，有的是不稳定的。最近，碰到了一个由 Chrome V8 不稳定排序算法引发的 Bug。

先说结论，Chrome 70 以下版本的 Array.prototype.sort，对于长度大于 10 个的数组采用的是快速排序，它是一种不稳定的排序算法。在 Chrome 70 之后，采用了稳定的TimSort算法。

事故代码

出现问题的是一个有以下基本逻辑的 React Hooks 组件：

  1. 有一个降序排列的数组，从第一项开始按序轮播，间隔 5 秒。
  2. useEffect 中监听数组，数组改变后自动高亮到第一个选项，因为认为这是新的数据了。
  3. render 方法中再次进行了排序。
  4. 可自由点击其他条目，高亮点击项。

由于平时开发都使用版本较新的 Chorme，开发过程中一直没发现这个组件有问题。偶然间在一个 64 版本的 Chrome 浏览器上测试时，出现了严重的 Bug：

  1. 点击其他条目，总是瞬间跳回并选中第一个。
  2. 每隔五秒，轮播到下一项到瞬间，跳回并选中第一个。
  3. 出现上述现象的过程中，伴随这某些数值相等到条目随机跳动。

事故原因

经过排查，发现问题的主要原因是排序算法的不稳定性。不稳定的排序，造成了相同的数组，在每次排序后，值相等的几个条目之间，顺序不一致，触发了 effect 逻辑。因此，在 sort 采用的是不稳定排序算法的浏览器中，都会出现上述问题。

还有一个问题是，在 render 方法中，执行了排序操作。它本意是为了保险，再次对数组进行了排序。因为排序不稳定，每次计算出的数组内容都是不同的（相同项前后两次顺序不一致）。这里每次渲染都重新计算，造成了一定不必要的开销，应在上层业务组件中处理一次排序即可。

通过这个网站，可以测试你浏览器的排序是不是稳定的。

排序算法

既然碰到了这个问题，顺便复习一下排序算法。稳定的排序算法有：冒泡排序、归并排序和插入排序等。不稳定的则有选择排序、快速排序、希尔排序、堆排序。

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const bubbleSort = arr => {
  if (!Array.isArray(arr)) {
    return [];
  }

  // 执行length - 1趟就可以了
  const len = arr.length - 1;
  for (let i = 0; i < len; i += 1) {
    for (let j = 0; j < len - i; j += 1) {
      const one = arr[j];
      const two = arr[j + 1];
      if (one > two) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}