什么是洗牌算法

简单来说
洗牌算法是一个用来将一个有限集合生成一个随机排列的算法（数组随机排序）
这个算法生成的随机排列是等概率的

再简单一点，就是将一个数组打乱

伪随机（概率）
真随机（几率）

所谓伪随机，是指概率事件，就是出现得并不规律，但是大致上就是这么多次数。比如1％，如果是每100次为一周期，那么1％意味着，尽管你不确定这1次究竟会什么时候出现，但100次中必然出现1次，不多一次也不会少一次。概率事件之间相互影响，一旦这一次没有触发，那么下一次触发的概率就会变大

而真随机则是指几率。比如1％的几率，意味着你这次触发特殊事件是1％的可能性，下次也是，每一次都是。如果你这次失败，下次依然保持在1％的可能性。还是上面的例子，1%的几率，100次中可能出现100次，也可能1次都不会出现，几率事件不会互相影响，因为每一次都是一个独立的事件

Fisher–Yates shuffle 洗牌算法

Fisher–Yates shuffle 洗牌算法原始版

• 写下从 1 到 N 的数字
• 取一个从 1 到 N 的数字的随机数 k
• 从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
• 重复第 2 步，直到所有的数字都被取出
• 第 3 步写出的这个序列，现在就是原始数字的随机排列

计算机会花很多无用的时间去计算上述第 3 步的剩余数字

Fisher–Yates shuffle 洗牌算法进化版

在每次迭代时将随机选出的这个数字排到数组的最后

时间复杂度是指执行算法所需要的计算工作量
空间复杂度是指执行这个算法所需要的内存空间