三种洗牌算法shuffle

科技前沿 • 2025-03-24 15:41 • 阅读 27

大家好，我是讯享网，很高兴认识大家。

1. 背景

笔试时，遇到一个算法题：差不多是在n个不同的数中随机取出不重复的m个数。洗牌算法是将原来的数组进行打散，使原数组的某个数在打散后的数组中的每个位置上等概率的出现，刚好可以解决该问题。

2. 洗牌算法

由抽牌、换牌和插牌衍生出三种洗牌算法，其中抽牌和换牌分别对应Fisher-Yates Shuffle和Knuth-Durstenfeld Shhuffle算法。

2.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取出的数字序列便是一个打乱了的数列。

下面证明其随机性，即每个元素被放置在新数组中的第i个位置是1/n（假设数组大小是n）。

证明：一个元素m被放入第i个位置的概率P = 前i-1个位置选择元素时没有选中m的概率 * 第i个位置选中m的概率，即

#define N 10 #define M 5 void Fisher_Yates_Shuffle(vector<int>& arr,vector<int>& res) { srand((unsigned)time(NULL)); int k; for (int i=0;i<M;++i) { k=rand()%arr.size(); res.push_back(arr[k]); arr.erase(arr.begin()+k); } }

讯享网 时间复杂度为O(n*n),空间复杂度为O(n).

三种洗牌算法shuffle

1. 背景

2. 洗牌算法

2.1 Fisher-Yates Shuffle算法

相关推荐