问题背景

有这样一个问题：给定一个长度为 n 的数组，你的任务是打乱该数组，保证每个元素出现在任意位置的概率相同，也就是在 n! 个排列中，每一个排序出现的概率相同。

很容易想到的方法是每次随机选出一个未被选过的元素，也就是说第一次有 n 种选择，第二次有 n-1 种选择，以此类推。使用这种方式时要么每次选出元素后都该把元素删除，接下来缩小随机数的生成范围；要么不删除元素，但是产生的随机数是已经选过的元素时，还要再次产生随机数。无论是哪种方式，时间复杂度都不只 O(n)。

这时就乱到洗牌算法出场了，它能够在 O(n) 时间复杂度下打乱数组。

算法过程及实现

洗牌算法有好几种写法，现在看一下最常见的写法：

假设数组长度为 n，从前往后迭代数组，对于第 i 个元素，生成一个 [i, n) 的随机数，然后将当前元素和随机数下标对于所对应元素交换。

这种方法的代码实现如下：

/**
 * 获得 [start, end) 中的一个随机数
 */
private int randRange(int start, int end) {
    return random.nextInt(end - start) + start;
}

/**
 * 交换 nums[i] 和 nums[j]
 */
private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

/**
 * 打乱数组 nums
 */
private void shuffle(int[] nums) {
    int n = nums.length;    // 数组长度
    for (int i = 0; i < n; i++) {
        // 将当前元素和 [i, n) 中的随机数所对应的元素交换
        swap(nums, i, randRange(i, n));
    }
}

除了这种写法外，还可以从后往前遍历，这时将当前元素和 [0, i+1) 中的随机数所对应的元素交换：

1
2
3

for (int i = n-1; i >= 0; i--) {
    swap(nums, i, randRange(0, i+1));
}

另外，以上两种情况的最后一种情况都可以不纳入循环，因为最后一种情况只能是自己和自己交换。

算法证明

以第一种写法为例，假设数组的长度为 n，只要证明一个元素 m 放入第 i 个位置的概率为 1/n 即可，证明过程如下：

前 i-1 个位置没有选中 m 的概率为 p1 = (n-1)/n x (n-2)/(n-1) x…x (n-i)/(n-i+1) = (n-i)/n
第 i 个位置选中 m 的概率为 p2 = 1/(n-i)
第 i 个位置选中 m 后，后面的元素的交换不会影响到 m，所以元素 m 放入第 i 个位置的概率为 p1 x p2 = 1/n，证毕。

另一种写法的证明类似，不再多说。

参考

三种洗牌算法shuffle