洗牌算法 | Fisher–Yates shuffle

费雪耶茨算法（Fisher-Yates shuffle），用来将一个集合随机排列，常用在扑克洗牌，打乱抽奖奖池等场景中。

Fisher-Yates 洗牌算法是由 Ronald A.Fisher 和 Frank Yates 于1938年发明的，后来被Knuth在书中介绍，很多人直接称Knuth洗牌算法， Knuth大家应该比较熟悉，《The Art of Computer Programming》作者，算法理论的创始人。

使用 Fisher-Yates 算法打乱顺序，得到的每种排列都是等概率的。Fisher-Yates 算法运行时不占用额外的存储空间，消耗的时间正比于需要打乱的数的数量，改良后的算法时间复杂度仅有O(n)。

等概率：洗牌算法有些人也称等概率洗牌算法，其实发牌的过程和我们抽签一样的，大学概率论讲过抽签是等概率的，同样洗牌算法选中每个元素是等概率的。

用洗牌算法思路从1、2、3、4、5这5个数中，随机取一个数

第一次随机抽取到4这个元素，4被抽中的概率是1/5
第二次随机抽取到5这个元素，5被抽中的概率是1/4 * 4/5 = 1/5
第三次随机抽取到2这个元素，2被抽中的概率是1/3 * 3/4 * 4/5 = 1/5
第四次随机抽取到1这个元素，1被抽中的概率是1/2 * 1/3 * 3/4 * 4/5 = 1/5
第五次随机抽取到3这个元素，3被抽中的概率是1/2 * 1/3 * 3/4 * 4/5 = 1/5

时间复杂度为O(n*n),空间复杂度为O(n)。

在上面的介绍的发牌过程中， Knuth 和 Durstenfeld 在Fisher 等人的基础上对算法进行了改进，在原始数组上对数字进行交互，省去了额外O(n)的空间。

该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。

在54张牌中随机选一张，将这张牌与第一张交换顺序
在剩下的53张中继续随机选取一张与第二张牌进行交换
往复上述过程，直至最后一张；

时间复杂度为O(n)，空间复杂度为O(1)，缺点必须知道数组长度n。

打乱一维数组

function shuffle(arr) {
  for(let i = arr.length - 1; i > 0; i--){
    let j = Math.floor(Math.random() * (i + 1));
    [arr[j], arr[i]] = [arr[i], arr[j]];
  }
}

洗牌算法

洗牌算法 | Fisher–Yates shuffle

打乱一维数组

生成雷区