洗牌算法/Fisher-Yates Shuffle

忆星辰

算法

发布于：2019年9月20日

字数：600字

时长：2分钟

次阅读

洗牌算法/Fisher-Yates Shuffle

洗牌算法

在游戏开发中，经常会遇到需要将一个数组打乱的情况，例如，在一个卡牌系统中需要做一个抽卡，给你8张卡牌，从中抽取一张，并获得奖励：

使用洗牌算法打乱卡牌中的奖励，实现随机抽奖的效果：

Fisher-Yates Shuffle算法

费舍尔·耶茨洗牌算法的做法是：给出数组Array，数组长度为n，取数组最后一个值M，再从数组的前n-1个元素中随机取一个值N，与最后一个值交换位置M，再取数组倒数第二个值N1，在前n-2各元素中随机取一个值M1与N1交换位置，依次取完剩下的值，完成数组打乱，算法的时间复杂度为O(n)。
JS实现：

let arr = [0, 1, 2, 3, 4];
for(let i  = 0;   i< arr.length;i++){
    const random = Math.floor(Math.random() * (i+1));
    [arr[i], arr[random]] = [arr[random], arr[i]];
}

简单的打乱算法

还有另一种简单的随机打乱算法，虽然也可以实现随机打乱数组，但是在大量的结果上并不能实现完全的随机，原因是JS源码中的sort()方法：

v8 在处理 sort 方法时，使用了插入排序和快排两种方案。当目标数组长度小于10时，使用插入排序；反之，使用快排。

其实不管用什么排序方法，大多数排序算法的时间复杂度介于 O(n) 到 O(n2) 之间，元素之间的比较次数通常情况下要远小于 n(n-1)/2，也就意味着有一些元素之间根本就没机会相比较（也就没有了随机交换的可能），这些 sort 随机排序的算法自然也不能真正随机。通俗的说，其实我们使用 array.sort 进行乱序，理想的方案或者说纯乱序的方案是：数组中每两个元素都要进行比较，这个比较有 50% 的交换位置概率。如此一来，总共比较次数一定为 n(n-1)。而在 sort 排序算法中，大多数情况都不会满足这样的条件。因而当然不是完全随机的结果了。
JS实现：