之前写斗地主的时候简单写了一个洗牌函数，基本思路是先产生一个顺序数组，遍历数组，每次产生一个（1~n）随机数，把这个随机数作为下标取出数组里的数与当前位置的数交换。
当时也没多想，反正能打乱数组顺序就行，后来跟师兄吃饭的时候聊起来，说到面试里也出现过洗牌算法，问我怎么保证这个算法得到的数组是完全随机的（即等概），我一时竟不知怎么证明。
回来后上网找了一下，才发现原来这个算法竟然不是完全随机的。
下面是一些思考和总结：（假设牌数为n）
- 首先最容易想到的一种等概的算法就是每次从数组里随机不放回地取出一个数，循环n次，刚好把数取完。
这个算法难点在于如何实现不放回。常规做法有两种：a.删掉。但如果是采用数组方式存储需要移动后面的所有数，而如果采用链表每次遍历也会影响效率，所以这种方式不可取。b. 标记。如果取到的数已标记，则重新产生随机数。这种方式在于越到后面，标记的位置越多，产生新的随机数越难，也不可取。
然后我就看到了这篇：
