洗牌算法

引言

首先看一道題目：有一個大小為100的數(shù)組，里面的元素是從 1 到 100，隨機從數(shù)組中選擇50個不重復數(shù)。

用 Math.random() * 100 ，就可以拿到一個 0 到 99 的隨機數(shù)，是不是重復50次就可以了？當然不是，假如，第一次隨機到5，第二次如果再一次隨機到5的話，要求是選擇不重復的數(shù)，所以要選出50個不重復的數(shù)的話，隨機次數(shù)遠遠大于50，因為越到后面隨機到的數(shù)與前面選出的數(shù)重復的概率越大。

怎么解決呢？大家都玩過或見過發(fā)牌，54張牌，發(fā)一張牌，發(fā)牌人手里就少一張，直至將所有牌都發(fā)完。

同樣上面的問題也可以這樣解決，第一次隨機到一個數(shù)后，將這個數(shù)取出來，再從剩下的99個數(shù)字里隨機取出第二個數(shù)，這樣隨機50次取出的書就不會重復，這就是今天的主題：洗牌算法

洗牌算法

Fisher-Yates洗牌算法是由 Ronald A.Fisher和Frank Yates于1938年發(fā)明的，后來被Knuth在書中介紹，很多人直接稱Knuth洗牌算法， Knuth大家應(yīng)該比較熟悉，《The Art of Computer Programming》作者，算法理論的創(chuàng)始人。我們現(xiàn)在所使用的各種算法復雜度分析的符號，就是他發(fā)明的。

等概率：洗牌算法有些人也稱等概率洗牌算法，其實發(fā)牌的過程和我們抽簽一樣的，大學概率論講過抽簽是等概率的，同樣洗牌算法選中每個元素是等概率的。

用洗牌算法思路從1、2、3、4、5這5個數(shù)中，隨機取一個數(shù)

4被抽中的概率是1/5

5被抽中的概率是1/4*4/5=1/5

2被抽中的概率是1/3*3/4*4/5=1/5

1被抽中的概率是1/2*1/3*3/4*4/5=1/5

3被抽中的概率是1*1/2*1/3*3/4*4/5=1/5

時間復雜度為O(n*n),空間復雜度為O(n)

算法思路：

在上面的介紹的發(fā)牌過程中， Knuth 和 Durstenfeld 在Fisher 等人的基礎(chǔ)上對算法進行了改進，在原始數(shù)組上對數(shù)字進行交互，省去了額外O(n)的空間。該算法的基本思想和 Fisher 類似，每次從未處理的數(shù)據(jù)中隨機取出一個數(shù)字，然后把該數(shù)字放在數(shù)組的尾部，即數(shù)組尾部存放的是已經(jīng)處理過的數(shù)字。

在54張牌中隨機選一張，將這張牌與第一張交換順序

在剩下的53張中繼續(xù)隨機選取一張與第二張牌進行交換

直至最后一張。

時間復雜度為O(n),空間復雜度為O(1),缺點必須知道數(shù)組長度n。

代碼：

void Knuth_Durstenfeld_Shuffle(vector<int>&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);
}