洗牌算法

[myLightLin]

思想

洗牌算法有很多实现，比较著名的是 Fisher-Yates 洗牌算法（也称为 Knuth 洗牌算法），它的基本原理是：从尾部开始往前遍历数组元素，在索引 0 到 i 之间生成一个随机索引 j，然后交换数组 i 和 j 位置的元素，随着 i 不断往前缩减，到第一个元素时，整个数组已经被打乱好了。

代码

以下是 JavaScript 实现：

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

测试一下：

const arr = [1, 2, 3, 4, 5]
const shuffled = shuffle(arr)
console.log(shuffled)

在 Chrome 控制台执行的时候，发现报错了：

原因是：

  for (let i = list.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));  //  !! 这里要加分号
    [list[i], list[j]] = [list[j], list[i]]
  }

再次执行，结果：

表现正常了。