如何实现一个公平的洗牌算法

问题描述：

设计一个公平的洗牌算法

就像打牌的时候一样，我们洗牌之后并不知道牌的顺序变成什么样，当然，前提是这个牌洗转了。正如这个问题，核心的点是公平，怎样才叫公平呢？

暴力解法：

n个数的全排列有n！个，那么随机拿出这里面任意一个结果也算公平。但是它的时间复杂度是O(n!)！原地爆炸boomboom

Knuth 洗牌算法:

至于Knuth何许人也，感兴趣的可以去查一下。微软是 IT 界老大的年代，比尔盖茨直接说，如果你看完了Knuth写的《The Art of Computer Programming》第一卷本，请给我发简历。

生成的排列中，也就是我们的结果，每一个元素都能独立等概率的出现在每一个位置。或者反过来，每一个位置都能独立等概率的放置每个元素。

for(int i = n - 1; i >= 0 ; i -- )
    swap(arr[i], arr[rand(0, i)]) // rand(0, i) 生成 [0, i] 之间的随机整数

很好理解，i从后向前，每次生成0~i之间的一个随机数，然后将i和这个随机数交换， swap(arr[i], arr[rand(0, i)]) 看出，i可以跟自己交换。（假想rand()无偏）

为什么公平呢？

对于生成的排列，每一个元素都能等概率的出现在每一个位置

示例：现有6个数从小到大排列：1 2 3 4 5 6

• 首先随机选择一个数和6进行交换，假设是3

因为可以和自己交换，我们可以知道3出现在最后的概率是1/6

• 选择到5，假设和2交换

同样的第一轮2没有被选中，那么它逃掉的概率是5/6，第二轮被选中的概率是1/5，那么它被选中的概论等于5/6x1/5=1/6

• 到4，假设和1交换

1被选中的概率等于5/6x4/5x1/4=1/6

看到这里，应该知道后面的概率也是1/6了，所以这个算法是公平的，可以自己去实验一下。最后这个算法的时间复杂度是O(n)