Array shuffle 算法

Array shuffle 是一个很常用的算法，比如说扑克牌游戏的洗牌就用到了这个算法。lodash 就有 shuffle 的实现，本文尝试手动写一个 Array shuffle，希望对您有点启发。

代码实现

slice

function shuffle(arr = [], n = 2) {
  const result = [];
  for (let i = 0; i < n; i++) {
    const len = arr.length;
    const index = Math.floor(Math.random() * len);
    result.push(...arr.splice(index, 1));
  }
  return result;
}

function handleClick() {
  const list = document.getElementById("numbers");
  const arr = Array.from({ length: 9 }, (v, i) => i + 1);
  list.innerHTML = shuffle(arr, 6)
    .map((v) => `<li>${v}</li>`)
    .join("\n");
}
handleClick();

• 参数 arr 可为任意数组，Array.from({ length: 9 }, (v, i) => i + 1); 可以生成 1 ~ 9 的数组，不用ES6的话可以用循环来实现
• 参数 n 为正整数，表示从参数 arr 中取出几个元素
• 数组循环遍历时，splice(index, 1) 方法会每次都删除已取出的元素并改变原数组，下一次循遍历的是新数组，从而保证取出的元素不重复

虽然已经满足了随机性的要求，但是这种实现方式在性能上并不好，需要遍历几次数组，并且还要对数组进行 splice 操作。

那么如何高性能的实现真正的乱序呢？而这就要提到经典的 Fisher–Yates 算法。

Fisher–Yates

为什么叫 Fisher–Yates 呢？ 因为这个算法是由 Ronald Fisher 和 Frank Yates 首次提出的。

这个算法其实非常的简单，就是将数组从后向前遍历，然后将当前元素与随机位置的元素进行交换。

function shuffle(arr) {
  let n = arr.length;
  while (n> 1) {
    let i = Math.floor(Math.random() * n--);
    [arr[i], arr[n]] = [arr[n], arr[i]];
  }
  return arr;
}

而且 Fisher–Yates 算法只需要通过一次遍历即可将数组随机打乱顺序，性能极为优异，但如果只是取部分元素，这种算法不是很合适。

总结

• 对数组随机不重复取部分元素，使用 slice 方法
• 对数组随机不重复，使用 Fisher–Yates 算法

参看实例

访问 Codepen 查看代码及最终效果。