洗牌算法好在哪里？-一一网

参考：《三种洗牌算法shuffle》作者：lyz_cs

引子

leetcode 384 打乱数组，要求将数组打乱，使得每个数字出现在数组任一位置的概率相等。

没有接触过洗牌算法的我，初一接触这个问题写出了如下的代码：

public int[] shuffle() {
    Random r = new Random();
    for(int i=0;i<nums.length;i++){
        int j = r.nextInt(nums.length-1);
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
复制代码

写完之后，提交正确。看评论区，大佬们给出了一种很奇怪的算法（其实就是K-D洗牌算法）：

public int[] shuffle() {
        Random r = new Random();
        //随机出一个符合范围的数,交换两个位置的元素,再不断的缩小范围
        for(int i=n-1;i>0;i--){
            int j = r.nextInt(i+1);
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }
复制代码

看完之后，大为不解。从后往前遍历，随机与自身以及之前的数字交换，为什么要这么写？

我的写法，将每个数字随机与0到n-1的位置的数字交换，显然结果也是平均分布（用matlab进行多次仿真，也支持这一结果），思维难度也小，为何要多此一举？查看了很多文章，了解了经典的洗牌算法，却仍然没有解除我的疑惑。

接下来，先补充介绍几种经典的洗牌算法，然后在最后给出答案。已经掌握的朋友可以直接跳到最后。

经典的 Shuffle 洗牌算法

Fisher-Yates Shuffle算法

最早提出这个洗牌方法的是 Ronald A. Fisher 和 Frank Yates，即 Fisher–Yates Shuffle，其基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中，具体如下：

  1. 初始化原始数组和新数组，原始数组长度为n(已知)；

  2. 从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（假设数组从0开始）；

  3. 从剩下的k个数中把第p个数取出；

  4. 重复步骤2和3直到数字全部取完；

  5. 从步骤3取出的数字序列便是一个打乱了的数列。

 证明：类似于抓阄的概率是相同的，在新数组的每个位置上，每个数字被抽到的概率是相同的。
复制代码

Knuth-Durstenfeld (努斯-杜斯滕费尔德) Shuffle

Knuth 和 Durstenfeld 在Fisher 等人的基础上对算法进行了改进，在原始数组上对数字进行交换，省去了额外O(n)的空间。该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。
算法步骤为：

1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
2. 生成一个从 0 到 n - 1 的随机数 x；
3. 输出 arr 下标为 x 的数值，即为第一个随机数；
4. 将 arr 的尾元素和下标为 x 的元素互换；
5. 同2，生成一个从 0 到 n - 2 的随机数 x；
6. 输出 arr 下标为 x 的数值，为第二个随机数；
7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；
 ……
如上，直到输出 m 个数为止
对于arr[i],洗牌后在第n-1个位置的概率是1/n（第一次交换的随机数为i）
在n-2个位置概率是[(n-1)/n] * [1/(n-1)] = 1/n，（第一次交换的随机数不为i，第二次为arr[i]所在的位置（注意，若i=n-1，第一交换arr[n-1]会被换到一个随机的位置））
在第n-k个位置的概率是[(n-1)/n] * [(n-2)/(n-1)] *...* [(n-k+1)/(n-k+2)] *[1/(n-k+1)] = 1/n
（第一个随机数不要为i，第二次不为arr[i]所在的位置(随着交换有可能会变)……第n-k次为arr[i]所在的位置）.
复制代码

Inside-Out Algorithm

Knuth-Durstenfeld Shuffle 是一个内部打乱的算法，算法完成后原始数据被直接打乱，尽管这个方法可以节省空间，但在有些应用中可能需要保留原始数据，所以需要另外开辟一个数组来存储生成的新序列。

	Inside-Out Algorithm 算法的基本思思是从前向后扫描数据，把位置i的数据随机插入到前i个（包括第i个）位置中（假设为k），这个操作是在新数组中进行，然后把原始数据中位置k的数字替换新数组位置i的数字。其实效果相当于新数组中位置k和位置i的数字进行交互。
	如果知道arr的lengh的话，可以改为for循环，由于是从前往后遍历，所以可以应对arr[]数目未知的情况，或者arr[]是一个动态增加的情况。
证明如下：
原数组的第 i 个元素（随机到的数）在新数组的前 i 个位置的概率都是：(1/i) * [i/(i+1)] * [(i+1)/(i+2)] *...* [(n-1)/n] = 1/n，（即第i次刚好随机放到了该位置，在后面的n-i 次选择中该数字不被选中）。
原数组的第 i 个元素（随机到的数）在新数组的 i+1 （包括i + 1）以后的位置（假设是第k个位置）的概率是：(1/k) * [k/(k+1)] * [(k+1)/(k+2)] *...* [(n-1)/n] = 1/n（即第k次刚好随机放到了该位置，在后面的n-k次选择中该数字不被选中）。
复制代码