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