Fisher-Yates Shuffle算法

最早的洗牌算法，其原理是从原始数组中随机取一个之前没取过的数字到新的数组中。时间复杂度 O(n^2)，空间复杂度 O(n)。

特点：

随机性。
等概率，即每种结果的出现概率都应相同。

缺点：

必须知道数组的长度。

举例👇

假设有一副扑克牌 54张，现在要你把它洗乱，且每张牌都不能在原来的位置，要求是随机的。

算法步骤

初始化一个数组大小为 n 的数组 arr，已知的。
从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字 r。
从剩下的 k 个数中把第 r 个数取出放到新数组里。
重复2、3步骤，直到数字全部取完。

javascript

// 第一步
const poker = [
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
  23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41,
  42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54,
]


function shuffle(arr) {
  let res = []

  // 第四步
  while(arr.length > 0) {
    // 第二步
    const r = parseInt(Math.random() * arr.length)
    // 第三步
    res.push(arr.splice(r, 1)[0])
  }

  return res
}

shuffle(poker)

进阶

🔗 改进洗牌算法之Knuth-Durstenfeld Shhuffle算法

Fisher-Yates Shuffle算法 ​

Fisher-Yates Shuffle算法