洗牌算法/Fisher-Yates Shuffle

洗牌算法

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

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

Fisher-Yates Shuffle算法

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

1
2
3
4
5
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实现:

1
2
const arr = [0, 1, 2, 3, 4];
arr.sort(() => Math.random() > 0.5);

评论