洗牌算法
引言
首先看一道題目：有一個(gè)大小為100的數(shù)組，里面的元素是從 1 到 100，隨機(jī)從數(shù)組中選擇50個(gè)不重復(fù)數(shù)。
用 Math.random() * 100 ，就可以拿到一個(gè) 0 到 99 的隨機(jī)數(shù)，是不是重復(fù)50次就可以了？當(dāng)然不是，假如，第一次隨機(jī)到5，第二次如果再一次隨機(jī)到5的話，要求是選擇不重復(fù)的數(shù)，所以要選出50個(gè)不重復(fù)的數(shù)的話，隨機(jī)次數(shù)遠(yuǎn)遠(yuǎn)大于50，因?yàn)樵降胶竺骐S機(jī)到的數(shù)與前面選出的數(shù)重復(fù)的概率越大。
怎么解決呢？大家都玩過或見過發(fā)牌，54張牌，發(fā)一張牌，發(fā)牌人手里就少一張，直至將所有牌都發(fā)完。
同樣上面的問題也可以這樣解決，第一次隨機(jī)到一個(gè)數(shù)后，將這個(gè)數(shù)取出來，再從剩下的99個(gè)數(shù)字里隨機(jī)取出第二個(gè)數(shù)，這樣隨機(jī)50次取出的書就不會(huì)重復(fù)，這就是今天的主題：洗牌算法
洗牌算法
Fisher-Yates洗牌算法是由 Ronald A.Fisher和Frank Yates于1938年發(fā)明的，后來被Knuth在書中介紹，很多人直接稱Knuth洗牌算法， Knuth大家應(yīng)該比較熟悉，《The Art of Computer Programming》作者，算法理論的創(chuàng)始人。我們現(xiàn)在所使用的各種算法復(fù)雜度分析的符號(hào)，就是他發(fā)明的。
等概率：洗牌算法有些人也稱等概率洗牌算法，其實(shí)發(fā)牌的過程和我們抽簽一樣的，大學(xué)概率論講過抽簽是等概率的，同樣洗牌算法選中每個(gè)元素是等概率的。
用洗牌算法思路從1、2、3、4、5這5個(gè)數(shù)中，隨機(jī)取一個(gè)數(shù)
第一次隨機(jī)抽取到4這個(gè)元素4被抽中的概率是1/5
第二次隨機(jī)抽取到5這個(gè)元素5被抽中的概率是1/4*4/5=1/5
第三次隨機(jī)抽取到2這個(gè)元素2被抽中的概率是1/3*3/4*4/5=1/5
第四次隨機(jī)抽取到1這個(gè)元素1被抽中的概率是1/2*1/3*3/4*4/5=1/5
第五次隨機(jī)抽取到3這個(gè)元素3被抽中的概率是1*1/2*1/3*3/4*4/5=1/5
時(shí)間復(fù)雜度為O(n*n),空間復(fù)雜度為O(n)
算法思路：
在上面的介紹的發(fā)牌過程中， Knuth 和 Durstenfeld 在Fisher 等人的基礎(chǔ)上對(duì)算法進(jìn)行了改進(jìn)，在原始數(shù)組上對(duì)數(shù)字進(jìn)行交互，省去了額外O(n)的空間。該算法的基本思想和 Fisher 類似，每次從未處理的數(shù)據(jù)中隨機(jī)取出一個(gè)數(shù)字，然后把該數(shù)字放在數(shù)組的尾部，即數(shù)組尾部存放的是已經(jīng)處理過的數(shù)字。
在54張牌中隨機(jī)選一張，將這張牌與第一張交換順序
在剩下的53張中繼續(xù)隨機(jī)選取一張與第二張牌進(jìn)行交換
直至最后一張。
時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1),缺點(diǎn)必須知道數(shù)組長(zhǎng)度n。
代碼：
void?Knuth_Durstenfeld_Shuffle(vector&arr)
{
?for?(int?i=arr.size()-1;i>=1;--i)
?{
??srand((unsigned)time(NULL));
??swap(arr[rand()%(i+1)],arr[i]);
?}
}?
洗牌算法生成雷區(qū)：
將排列好的雷，用洗牌算法打亂生成雷區(qū)圖
for(int?i=N*M-1;i>=0;i--)
{
???int?iX?=?i/M;????//iX為X坐標(biāo)
???int?iY?=?i%M;????//iY為Y坐標(biāo)
???
???int?randNumber?=?(int)(Math.random()*(i+1));
???
???int?randX?=?randNumber/M;
???int?randY?=?randNumber%M;
???
???swap(iX,iY,randX,randY);
}
生成的雷區(qū)圖點(diǎn)【在看】是最大的支持?