圖解洗牌算法

引言

首先看一道題目：有一個(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ù)

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

時(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<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坐標(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);
}