大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
1. 问题描述
洗牌算法是常见的随机问题；它可以抽象成：得到一个M以内的所有自然数的随机顺序数组。
常见问题描述：
1.将自然数1 ～ 100随机插入到一个大小为100的数组，无重复元素
2. 1 ～ 52张扑克牌重新洗牌
什么是好的洗牌算法：
洗牌之后，如果能够保证每一个数出现在所有位置上的概率是相等的，那么这种算法是符合要求的；这在个前提下，尽量降低时间和空间复杂度。
2. 算法实现
第一个算法：
随机抽出一张牌，检查这种牌是否被抽取过，如果已经被抽取过，则重新抽取，知道找到没有被抽取的牌；重复该过程，知道所有的牌都被抽取到。
这种算法是比较符合大脑的直观思维，这种算法有两种形式：
1. 每次随机抽取后，将抽取的牌拿出来，则此时剩余的牌为(N-1)，这种算法避免了重复抽取，但是每次抽取一张牌后，都有一个删除操作，需要在原始数组中删除随机选中的牌(可使用Hashtable实现)
2. 每次随机抽取后，将抽取的符合要求的牌做好标记，但并不删除；与1相比，省去了删除的操作，但增加了而外的存储标志为的空间，同时导致可每次可能会抽取之前抽过的牌
这种方法的时间/空间复杂度都不好。
第二个算法：
每次随机抽出两张牌交换，交换一定次数后结束：
void shuffle(int* array, int len) { const int suff_time = len; for (int idx = 0; i < suff_time; i++) { int i = rand() % len; int j = rand() % len; int temp = array[i]; array[i] = array[j]; array[j] = temp; } }
这是一个常见的洗牌算法; 但是如何确定一个合适的交换次数?
假设交换了m此,则某张牌始终没有被交换的概率为 (n-2)/n * (n-2)/n, … …* (n-2)/n = ((n-2)/n)^m;我们希望其概率小于摸个值,求出m的解.假设概率小于1/1000,对于n=52,m大概为176,实际上远远大于数组的长度.
第三个算法:
该算法每次随机选取一个数，然后将该数与数组中最后(或最前)的元素相交换(如果随机选中的是最后/最前的元素，则相当于没有发生交换)；然后缩小选取数组的范围，去掉最后的元素,即之前随机抽取出的数。重复上面的过程，直到剩余数组的大小为1，即只有一个元素时结束：
void shuffle(int* array, int len)
{
int i = len;
int j = 0;
int temp= = 0;
if (i == 0)
{
return;
}
while (--i)
{
j = rand() % (i+1);
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
} 该算法的数学证明请参照具体的论文或者
博文;
该算法复杂度为O(n)，且各元素随机概率相等。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/191038.html原文链接：https://javaforall.net
![解决主页被 hao.360.cn 劫持 及 分析[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
