关于Random Shuffle

random shuffle指的是将一个数组里面的元素随机打乱得到一个新的数组。下面给出两种随机打乱算法的实现思路，在打乱效果上两种实现并没有本质上的区别。

1. 打乱算法一：

int random_shuffle(int[] a) {

    for(int i = 0; i < a.length; ++i) {

        int r = random(i, a.length);  // random(a, b) 返回一个随机的int值，该值位于[a, b)之间

        swap(a[i], a[r]);

    }

}

正确性： 使用“抽签公平性”可证明之

2. 打乱算法二：

int random_shuffle(int[] a) {

    for(int i = 0; i < a.length; ++i) {

        int r = random(0, i + 1);  // random(a, b) 返回一个随机的int值，该值位于[a, b)之间

        swap(a[i], a[r]);

    }

}

正确性：

假设for循环执行k步之后，前k个全素已被正确的随机打乱，即对于原数组前k个元素中的任一个，其现在位于a[i], i ∈ [0, k - 1]的概率均为1 / k。那么当for循环执行完第k+1步之后，对于前k+1个元素，也会被正确的随机打乱。因为，由第k+1步的操作易知，对于第k+1个元素，其出现在[0...k]中某一位置的概率为1 / (k+1)，而对于前k个元素，经过第k+1步之后，其处于[0...k-1]中某个位置的概率为1/k * (1 - 1 /  (k + 1)) = 1 / (k + 1)，其处于位置k的概率为 1 / (k + 1)，因此对于前k个元素，其出现在[0...k]中任一位置的概率也为1 / (k + 1)。