请你说一说洗牌算法？

Answer 1

参考回答：

考察点：

公司：腾讯

1、Fisher-Yates Shuffle算法

最早提出这个洗牌方法的是 Ronald A. Fisher 和 Frank Yates，即 Fisher–Yates Shuffle，其基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中，具体如下：

1）初始化原始数组和新数组，原始数组长度为n(已知)。

2）从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（假设数组从0开始）。

3）从剩下的k个数中把第p个数取出。

4）重复步骤2和3直到数字全部取完。

5）从步骤3取出的数字序列便是一个打乱了的数列。

时间复杂度为O(n*n)，空间复杂度为O(n)。

2）Knuth-Durstenfeld Shuffle

Knuth 和 Durstenfeld 在Fisher 等人的基础上对算法进行了改进，在原始数组上对数字进行交互，省去了额外O(n)的空间。该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。

算法步骤为：

\1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；

\2. 生成一个从 0 到 n - 1 的随机数 x；

\3. 输出 arr 下标为 x 的数值，即为第一个随机数；

\4. 将 arr 的尾元素和下标为 x 的元素互换；

\5. 同2，生成一个从 0 到 n - 2 的随机数 x；

\6. 输出 arr 下标为 x 的数值，为第二个随机数；

\7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；

……

如上，直到输出m 个数为止

时间复杂度为O(n)，空间复杂度为O(1)，缺点必须知道数组长度n。