需求：设计一个公平的洗牌算法

思考：洗牌的结果是所有元素的一个排列。一副牌如果有 n 个元素，最终排列的可能性一共有 n! 个。公平的洗牌算法，应该能等概率地给出这 n! 个结果中的任意一个。 如思考虑到这一点，我们就能设计出一个简单的暴力算法了：对于 n 个元素，生成所有的 n! 个排列，然后，随机抽一个。 这个算法绝对是公平的。但问题是，复杂度太高。复杂度是多少呢？O(n!)。因为，n 个元素一共有 n! 种排列，我们求出所有 n! 种排列，至少需要 n! 的时间。所以，这个算法确实是公平的，但是，时间不可容忍。

我们再换一个角度思考“公平”这个话题。其实，我们也可以认为，公平是指，对于生成的排列，每一个元素都能独立等概率地出现在每一个位置。 或者反过来，每一个位置都能独立等概率地放置每个元素。

基于这个定义，我们就可以给出一个简单的算法了。说这个算法简单，是因为他的逻辑太容易了，就一个循环：

for(int i = n - 1; i >= 0 ; i -- )

swap(arr[i], arr[rand(0, i)]) // rand(0, i) 生成 [0, i] 之间的随机整数

这么简单的一个算法，可以保证上面我所说的，对于生成的排列，每一个元素都能独立等概率的出现在每一个位置。或者反过来，每一个位置都能独立等概率的放置每个元素。 大家可以先简单的理解一下这个循环在做什么。其实非常简单，i 从后向前，每次随机一个 [0...i] 之间的下标，然后将 arr[i] 和这个随机的下标元素，也就是 arr[rand(0， i)] 交换位置。 大家注意，由于每次是随机一个 [0...i] 之间的下标，所以，在每一轮，是可以自己和自己交换的。 这个算法就是大名鼎鼎的 Knuth-Shuffle，即 Knuth 洗牌算法。