数组乱序

[S-T-D]

• 微软调查案例
  • 在线验证
  • 原因分析
    • sort 的原理
    • random 乱序的原理
    • random 乱序不可靠的原因
• 可靠的乱序
  • 对 random 方法进行改造
  • Fisher–Yates shuffle
• 参考资料
   

数组乱序：就是将数组内所有元素的顺序打乱，使每个元素随机出现在每个位置。

抽奖和洗牌等场景都会涉及到乱序。

微软调查案例

这是一个被到处提及的案例，大意是微软曾做过一个关于不同浏览器的使用情况的调查，需要在网页上按随机的顺序显示 5 款浏览器，这里用到的随机算法是：

arr.sort(() => Math.random() - 0.5);

这个算法乍一看感觉可以满足需求，但其实并不能实现完全的随机打乱数组。

也就是说数组中的每个元素，并不会随机出现在每个位置，而是在某些位置会更容易出现，并不是完全意义上的随机打乱。

在线验证

Will It Shuffle? 是一个通过可视化验证数组乱序算法可靠性的网站。

选择上述介绍的算法，查看可视化效果：

简单地说，颜色越多、差异越大、越不均匀，就说明算法的可靠性越差，也就是没有实现真正的随机乱序。

作为对比，选择另一个算法 —— Fisher–Yates 查看一下效果：

通过图片就能感受到两个算法之间的差距，就不用多说了。

原因分析

sort 的原理

sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的。—— MDN。

sort 还可以接收一个函数（comprator）作为参数。

comprator 接收 a 和 b 两个参数，表示进行比较的两个元素。

comprator 的返回值如果大于 0，a 就排在 b 的后面；如果小于 0，a 就排在 b 的前面；如果等于 0，a 和 b 的位置保持不变。

random 乱序的原理

Math.random() 的值在 [0, 1) 之间，包含 0 不包含 1。

那么 Math.random() - 0.5 的值就在 [-0.5, 0.5) 之间，包含 -0.5，不包含 0.5。

所以 () => Math.random() - 0.5 的返回值大于 0 和小于 0 的概率各 50%。

该乱序算法的原理就是通过随机返回大于或小于 0 的值来将 a 和 b 的顺序打乱，从而将整个数组的顺序打乱。

random 乱序不可靠的原因

我们知道，sort 方法在内部使用的是快速排序和插入排序相结合的方式，当数组长度小于 10 的时候，采用插入排序进行排序。

举例说明：

const arr = [5, 4, 3];

// 用 sort 将 arr 排序需要多少次比较呢？
// 3 次，分别是：5 <=> 4，4 <=> 3，5 <=> 3

// 那如果传入生成随机数的比较函数给 sort，会进行多少次比较呢？
// 3 次或 2 次。因为插入排序在找到合适的位置以后就会停止比较，将元素插入到合适的位置
// 所以，进行了第二次比较后，因为比较函数返回的值是随机的，所以不确定是否还有后续比较
// 就可能提前终止比较的流程，较少了比较的次数
// 对于排序算法来说，较少了比较次数肯定无法将数组排序
// 同样，对于乱序来说，减少了一些元素之间的比较，同样也无法使数组真正乱序

 

可靠的乱序

对 random 方法进行改造

上面说到 random 方法不可靠的原因在于比较函数每次的返回值是随机的，对于同样的输入，输出不稳定。

基于这个思路，我们可以改造上述算法，让比较函数对于同样的输入，输出是不变的。

function  shuffle(array) {
    // 构建新数组，提前生成随机数
    const newArr = array.map(item => ({
        value: item,
        random: Math.random(),
    }));
    // 对于输入相同的情况下，比较函数的的输出是稳定的
    newArr.sort((a, b) => a.random - b.random);
    array.splice(0, array.length, ...newArr.map(item => item.value));
}

可视化效果：

Fisher–Yates shuffle

上面的方法虽然可以满足乱序的需求，但是性能并不好。

这个算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，然后在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。

举例：

const array = [6, 3, 7, 2, 1];

// 从后往前遍历，当前遍历元素为 v 
// v 为 1 的时候，从数组开始到 v（包括 v） 的范围内随机选择一个元素和 v 交换位置
// v 为 2 的时候，从数组开始到 v（包括 v） 的范围内随机选择一个元素和 v 交换位置
// 重复直到数组起始位置...

代码：

function shuffle(array) {
    let i = array.length, j, temp;
    while (i) {
        j = Math.floor(Math.random() * i--);
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

时间复杂度：O(n)，n 为数组长度。
空间复杂度：O(1)。

 

参考资料

Will It Shuffle?
关于JavaScript的数组随机排序
「前端进阶」数组乱序
如何将一个 JavaScript 数组打乱顺序？ - Lucas HC的回答 - 知乎
Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot