洗牌算法

为了保证打牌时的公平性，洗牌后的牌堆应当是完全随机的。

从概率的角度来说，牌堆可以看成一个编号为 $ 1 $ 到 $ n $ 的数的序列，这个序列的排列组合数为 $ n! $。

完全随机也就是说每一种排列组合出现的概率相等，概率为 $ \frac{1}{n!} $

朴素洗牌算法

所谓朴素，就是说每次从未取出的数中随机取出一个数，排成序列。

JavaScript的代码如下：

        
function naiveShuffle(array) {
  var shuffle = [];
  var n = array.length;
  var i;

  while (n) {
    // Pick a random element
    i = Math.floor(Math.random() * n--);

    // Add the element to new pack
    // Re-order the left elements
    shuffle.push(array.splice(i, 1));
  }

  return shuffle;
}

取第一个数时，从 $ n $ 个数中随机取一个数（有 $ n $ 种可能）；取第二个数时，从剩下的 $ n - 1 $ 个数中随机取一个数（有 $n - 1$ 种可能）；如此重复 $n$ 次，则可得到一个序列。

此序列的概率为 $ \frac{1}{n!} $ ，与完全随机的概率一致。

分析一下此算法的性能

空间: $ O(n) $, 需要一个额外的大小为 $ n $ 的空间存储结果

时间: $ O(n^{2}) $, while循环的复杂度为 $ O(n) $ , 循环内整理牌堆的复杂度也为 $ O(n) $。

Fisher-Yates算法

接下来介绍一种更为有效的算法。

        
function fisherYatesShuffle(array) {
  var n = array.length;
  var i;

  while (n) {
    // Pick a random element
    i = Math.floor(Math.random() * n--);

    // Swap the random element with element in position n.
    t = array[n];
    array[n] = array[i];
    array[i] = t;
  }

  return array;
}

从第 $ 1 $ 到 $ n $ 个数中随机选取一个数，和第 $ n $ 个数交换，每次将 $ n $ 的值减 $ 1 $ ，如此重复 $ n $ 次，则可得到一个序列。

此序列的概率同样为 $ \frac{1}{n!} $ 。

同样分析一下此算法的性能

空间: $ O(0) $, 因为将当前位置的数存放在与之交换的数的位置上，所以不需要额外的空间。

时间: $ O(n) $, while循环的复杂度为 $ O(n) $ , 循环内操作的复杂度为 $ O(1) $。