两种随机打乱算法（洗牌算法）

Ysu2008

数组 a 有 n 个元素，即  a[n] ，将 a 的元素次序随机打乱，要求满足条件：任何一个元素出现在任何一个位置的概率相等。

有如下两种随机交换法：
1)  for i:=1 to n do swap(a[i], a[random(1,n)]);
2)  for i:=1 to n do swap(a[i], a[random(i,n)]);

swap(x,y) 指将 x 与 y 位置的元素交换；random(m,n) 的作用是等概率产生 m 到 n之间的一个随机整数（含m,n）。

两种算法都是通过遍历数组位置，每到一个位置 x，随机产生另一个位置 y，然后将 x 与 y 的元素交换而实现；

方法 1 每次都是从全部位置中等概率随机产生 ，random(1,n) ；
方法 2 则是从余下未遍历位置中等概率随机产生 ，random(i,n) ；

咋一看，方法 1 似乎更优，因为它的随机位置产生较方法 2 对称。

然而，这是一个错觉，方法 2 更好，也就是更能满足等概率的条件，洗牌洗得更均匀。

可以通过模拟洗牌实验来证实这一点。

将去掉王牌的 52 张扑克牌洗一万次，记下每张牌出现在位置 1 的次数，然后作卡方等概率检验，如能通过检验则说明满足等概率的条件。

用方法 1 洗牌一万次，其皮尔逊卡方值竟高达 8207.5088 ，自由度 51 的卡方分布右侧 0.05 分位数仅为 68.669 ，显然每一张牌出现在位置 1 的概率是不相等的；

方法 2 洗牌一万次，皮尔逊卡方值为 37.924 , 没有落入拒绝域，方法 2 满足洗牌要求。

除了上面的交换洗牌法，还可以采用随机不放回抽牌法。但模拟洗牌表明，抽牌法须要抽两次才能使得皮尔逊卡方值小于拒绝域临界值，性能不及交换法。