洗牌算法

Fisher-Yates Shuffle 算法

该算法具体思想如下：

初始化原始数组和新数组，原始数组长度为 $n$ (已知)。
从还没处理的数组（假如还剩 $k$ 个）中，随机产生一个 $[0, k)$ 之间的数字 $p$（假设数组从0开始）。
从剩下的 $k$ 个数中把第 $p$ 个数取出。
重复步骤 2 和 3 直到数字全部取完。
从步骤 3 取出的数字序列便是一个打乱了的数列。

该算法时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

function shuffle(arr) {
  let originLen = arr.length;
  let len = arr.length;
  const res = [];
  for (let i = 0; i < originLen; i++) {
    const randomNum = Math.floor(Math.random() * len);
    const num = arr.splice(randomNum, 1)[0];
    len--;
    res.push(num);
  }
  return res;
}

Knuth-Durstenfeld Shuffle 算法

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

每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。

该算法具体思想如下：

建立一个数组大小为 $n$ 的数组 $arr$，分别存放 $1$ 到 $n$ 的数值。
生成一个从 $0$ 到 $n - 1$ 的随机数 $x$。
输出 $arr$ 下标为 $x$ 的数值，即为第一个随机数。
将 $arr$ 的尾元素和下标为 $x$ 的元素互换。
同 2，生成一个从 $0$ 到 $n - 2$ 的随机数 $x$。
输出 $arr$ 下标为 $x$ 的数值，为第二个随机数。
将 $arr$ 的倒数第二个元素和下标为 $x$ 的元素互换。

如上，直到输出 $m$ 个数为止。

该算法也是最经典最常用的洗牌算法。时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，缺点必须知道数组长度 $n$。

function shuffle(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    const randomNum = Math.floor(Math.random() * len);
    let tmp = arr[randomNum];
    arr[randomNum] = arr[len - 1];
    arr[len - 1] = tmp;
  }
  return arr;
}