先来思考一个问题：有一个大小为 100 的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 1 个数？
最简单的方法是利用系统的方法 Math.random() * 100 ，这样就可以拿到一个 0 到 99 的随机数，然后去数组找对应的位置就即可。
接下来在思考一个问题： 有一个大小为100的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 50 个数？
注意数字不能重复！
如果根据上面的思路，你第一想法是：随机 50 次不就行了？
但是，这样做有个很明显的 bug ：数字是会重复的。
修改一下？
弄一个数组，把每一次随机出来的数与前面的比较，看是否出现过。
这样是可以的！
但，还是有个小问题，考虑一下极端情况：有一个大小为100的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 99 个数。
如果按照上面的方法操作，越往后选择的数字跟前面已经挑选的数字重复的概率越高，这就会造成如果数组很大，选择的数字数目也很大的话，重复次数在量级上会很大。
这个时候就需要换一个思路，如果先将数组里面的元素打乱，那么按顺序选择前 50 个不就可以了？
是的！
但我们得注意什么叫乱？
一副扑克有 54 张牌，有 54! 种排列方式。所谓的打乱指的是，你所执行的操作，应该能够 等概率地生成 这 54! 种结果中的一种。
洗牌算法就能做到这一点。
洗牌算法
Fisher–Yates shuffle 算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。
这个算法很牛逼却很好理解，通俗的解释就是：将最后一个数和前面任意 n-1 个数中的一个数进行交换，然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换。。。
附：蓄水池算法
给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。
这个场景强调了3件事：
- 数据流长度N很大且不可知，所以不能一次性存入内存。
- 时间复杂度为O(N)。
- 随机选取m个数，每个数被选中的概率为m/N。
第1点限制了不能直接取N内的m个随机数，然后按索引取出数据。第2点限制了不能先遍历一遍，然后分块存储数据，再随机选取。第3点是数据选取绝对随机的保证。讲真，在不知道蓄水池算法前，我想破脑袋也不知道该题做何解。
int[] reservoir = new int[m]; // init for (int i = 0; i < reservoir.length; i++) { reservoir[i] = dataStream[i]; } for (int i = m; i < dataStream.length; i++) { // 随机获得一个[0, i]内的随机整数 int d = rand.nextInt(i + 1); // 如果随机整数落在[0, m-1]范围内，则替换蓄水池中的元素 if (d < m) { reservoir[d] = dataStream[i]; } }
我们来计算第i个最终落在蓄水池的概率，分两种情况：
$i > m$，$P(i最终落在蓄水池) = frac{m}{i+1} * frac{i+1}{i+2} * frac{i+2}{i+3} cdots frac{n-1}{n} = frac{m}{n}$（即第i次被换进去，之后都没有被换出来），是不是和上面的公式一摸一样。
另一种情况，i初始就在蓄水池，则$P(i最终落在蓄水池) = frac{m}{m+1} * frac{m+1}{m+2} cdots * frac{n-1}{n} = frac{m}{n}$（即每次都不被换出去）
因此，每个元素最终落在蓄水池的概率都是 $frac{m}{n}$.