洗牌算法

本文主要是介绍洗牌算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.从100张牌里随机抽一张，这很简单吧，rand随机就行了。

2.从100张牌中抽50张牌，要求不重复呢。最简单的思路就是反复rand，并且将rand存入到hash表中，如果重复就在来一次，直到50次不重复。

3.从100张牌中抽99张不同的牌呢，那2的思路就很困难了，越到后面重复的概率越大，越耗时间。

接下来就到洗牌算法登场了。

这个算法的核心思路就是：将最后一个数和前面任意 n-1 个数中的一个数进行交换（也可以不换），然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换，如此往复直到最后一个元素，就完成了洗牌，该算法保证了每个元素在每个位置的概率都是相等的。

我们举例子来说明：1，2，3，4，5

第一次交换，1，2，3，4，5出现在第五个位置的概率为1/5。假设我们交换的是2，序列变为1，5，3，4，2。

第二次交换，1，5，3，4出现在第四个位置的概率为1/4，同时第一次没有选中他们的概率为4/5，所以最后的概率还是1/5。假设交换的序列为4，5，3，1。

第三次交换，4，5，3出现在第三个位置的概率为1/3，同时需要乘上第一次没被选中和第二次没被选中的概率，分别为4/5和3/4。最后概率还是1/5。

相信后面不需要推演了，大家应该都能知道这个算法的厉害之处了。

代码：

for(int i = n-1; i >= 0 ; --i){
    swap(arr[i],arr[rand()%(i+1)]);
}

洗牌的速度是o(n)哦。

这篇关于洗牌算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！