洗牌算法

洗牌算法问题为：

有一个大小为 100 的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 1 个数？

最简单的方法是用rand()系统自动生成一个1-100的数，然后去数组找对应的位置即可。

进一步，问题扩展为：

有一个大小为100的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 50 个数？

（注意数字不能重复！）

最简单的方法随机 50 次，新建一个数组，把每一次随机的数都放到数组里，下一次随机就看这个数组里面有没有这数，有的话就继续随机，直到这个数组里面有 50 个数字就停止。

问题再次扩展为：

有一个大小为100的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 99 个数？

如果按照上面的方法操作，越往后选择的数字跟前面已经挑选的数字重复的概率就越高，这就会造成如果数组很大，选择的数字数目也很大的话，重复次数在量级上会很大。

这个时候就需要换一个思路，如果先将数组里面的元素打乱那么按顺序选择前 50 个不就可以了？

但是什么叫乱呢？

比如一副扑克有 54 张牌，有 54! 种排列方式，所谓的打乱指的是，你所执行的操作，应该能够等概率地生成这54!种结果中的任意一种，或者简单点说，我把54! 种排列方式全算出来，然后随机取一个也行，但是对n个元素求全排列时间复杂度可是o(n!)的，因为n! > 2^n，所以肯定超过指数爆炸了，这种算法是绝对不可取的！

洗牌算法就出现了（Knuth-Shuffle大神）。

算法可简单表述为：将最后一个数和前面任意 n-1 个数中的一个数进行交换（也可以不换），然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换，如此往复直到最后一个元素，就完成了洗牌，该算法保证了每个元素在每个位置的概率都是相等的。

为什么是相等的呢？可以举例说明！

比如12345是最初的排列，从最后一个数5开始。

第一轮：5跟12345换的概率都是相等的，比如随机出了2，因为下一轮要从倒数第二个开始了，所以2肯定就在最后一位了，现在就是15342，因为是五个数里面选一个，所以2在最后一位的概率就是1/5；

第二轮：不算最后一个数2，还剩1534，轮到4选一个，比如选了3，交换完就是1543，那么3出现在第4个位置的概率是多少呢？因为第一轮五个选一个没选中3的概率是4/5，这一轮是四个选一个，1/4，所以3在第四位的概率就是4/5 * 1/4 = 1/5；

第三轮：不算最后两个数32，还剩154，轮到4选一个，比如选了自己，交换完就还是154，那么4出现在第三个位置的概率就是，4/5（第一轮没选4）*3/4（第二轮没选4）*1/3（第三轮选了4） = 1/5；

以此类推，就会发现，每个元素在每个位置的概率都是1/5，真正的做到了乱！（当然这个东西可以用严谨的数学证明验证）

简易代码

for (int i = n - 1; i >= 0; i--) {
    swap(arr[i], arr[rand() % (i + 1)]);    //每次随机出0-i之间的下标
}

那这个算法有多快呢？

因为只是遍历一遍数组，所以算法是O(n)的，而且代码量相当少，膜拜。