🥧 一次意外的 Bug 竟然是因为它 ？！Array.sort 使用避坑
!本篇文章过于久远，其中观点和内容可能已经不准确，请见谅!~
当你想要排序的时候，肯定会需要用到 sort 方案，但是请切忌排序结果没问题，但是过程是一个黑盒。
需求是随机获得 0-16 的数字组合，用处是来打乱一副牌，但是需要保证两人相同的随机过程。所以做了一个种子随机数，两个人实现同样的打乱过程，初步想法。
于是：
// 得到一个种子随机数（只要随机，不需要均匀分布，所以直接 sin）const seedrandom = (seed: number): () => number => {let order = 0;return () => Math.abs(Math.sin(seed + order++))}// 生成一个 0-16 的随机序列，只要指定 seed，无论什么时候得到的都是这个结果const getRandom = seedrandom(10086);(new Array(16).fill(0).map((v, i) => i)).sort((a, b) => getRandom() > 0.5 ? 1 : -1)// -> [0, 1, 4, 2, 5, 7, 14, 9, 8, 11, 12, 13, 15, 10, 6, 3]
上面的程序在浏览器里面运行没问题，重复 n 次还是这个结果。
结果在测试的时候出现了问题，两个人的结果不同。排查了数据同步问题等，发现问题出在这个随机序列的生成上。怎么回事，相同的代码啊？？
把出问题的浏览器 chrome 62 跑一下：
const getRandom = seedrandom(10086);(new Array(16).fill(0).map((v, i) => i)).sort((a, b) => getRandom() > 0.5 ? 1 : -1)// -> [2, 11, 13, 7, 8, 9, 15, 1, 10, 4, 12, 3, 14, 5, 6, 0]
复现了问题，同时也能够在 chrome vs safari，或者 chrome 80 vs chrome 62，不同的浏览器上看到这个问题的出现，所以这个一定是浏览器引擎的问题。
找到问题的过程很简单，这里分析下：
// seedrandom 没问题const seedrandom = (seed: number): () => number => {let order = 0;return () => Math.abs(Math.sin(seed + order++))}const getRandom = seedrandom(10086);const orderedList = (new Array(16).fill(0).map((v, i) => i))// [ 0, 1, 2, 3,..., 15 ]const compareFunc = (a, b) => getRandom() > 0.5 ? 1 : -1// --- 以上都没问题，运行都相同// 经过这个函数调用输出就不一样了orderedList.sort(compareFunc)
之前有听说过排序算法在浏览器内部不同版本的不同实现，今天是着实遇到了。
具体来说，chrom v80 的 sort 和 chrom v62 的 sort 不同，导致调用 getRandom 的顺序不同，最后产生不同的结果：
// <-- v80([1,2,3,4]).sort((a, b) => {console.log(a, b)return a - b})// --> 输出2 13 24 3// <-- v62([1,2,3,4]).sort((a, b) => {console.log(a, b)return a - b})// --> 输出1 22 33 4
在知道这个问题之后，这个随机洗牌这么生成算法就是有问题的了，sort 本身是一个排序函数，实际引擎黑盒执行的时候，调用比较函数是不固定的，排序是从头到尾还是二分的顺序有不同的实现，不能作为可依赖的算法一部分。
// 最终洗牌算法变成了这样，不使用排序，而是直接取值，不依赖浏览器内部export const generateRandomArray = (seed: number, length: number) => {let orderedList = new Array(length).fill(0).map((v, i) => i)let output: number[] = []let getRandom = seedrandom(seed)for (let i = 0; i < length; i++) {const pick = Math.floor(getRandom() * orderedList.length)output.push(orderedList[pick])orderedList.splice(pick, 1)}return output}
先看下 MDN 文档：
里面就明确说这个排序的实现并不是每个浏览器都相同。
而我们看源码：
V8_6.2 内置的 js 方法实现：https://github.com/v8/v8/blob/6.2-lkgr/src/js/array.js#L1005
上面明确说了小于等于 10 的数组用插入排序，不然使用快速排序：
快排里面小于 10 会调用插入排序：
Stack Overflow 有指向文章 官方博客 ，明确说了:
Array.prototype.sort was among the last builtins implemented in self-hosted JavaScript in V8. Porting it offered us the opportunity to experiment with different algorithms and implementation strategies and finally make it stable in V8 v7.0 / Chrome 70.
V8 7.0 将排序算法改成了稳定排序。
在我们测试的 v8 8.0 sort 中：
具体就不分析了，tq 语言也没有高亮，反正就是算法的实现变更了：
最后就是这个排序算法的实现历史，不能依靠排序算法的过程黑盒来参与业务内容。
感谢您的阅读，本文由 Ubug 版权所有。如若转载，请注明出处：Ubug（https://ubug.io/blog/random-and-sort）
