C語言實作洗牌算法

引言

首先看一道題目：有一個大小為100的數組，裡面的元素是從 1 到 100，随機從數組中選擇50個不重複數。

用

Math.random() * 100

，就可以拿到一個 0 到 99 的随機數，是不是重複50次就可以了？當然不是，假如，第一次随機到5，第二次如果再一次随機到5的話，要求是選擇不重複的數，是以要選出50個不重複的數的話，随機次數遠遠大于50，因為越到後面随機到的數與前面選出的數重複的機率越大。

怎麼解決呢？大家都玩過或見過發牌，54張牌，發一張牌，發牌人手裡就少一張，直至将所有牌都發完。

同樣上面的問題也可以這樣解決，第一次随機到一個數後，将這個數取出來，再從剩下的99個數字裡随機取出第二個數，這樣随機50次取出的書就不會重複，這就是今天的主題：洗牌算法

洗牌算法

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

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

用洗牌算法思路從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)

算法思路：

在上面的介紹的發牌過程中， Knuth 和 Durstenfeld 在Fisher 等人的基礎上對算法進行了改進，在原始數組上對數字進行互動，省去了額外O(n)的空間。該算法的基本思想和 Fisher 類似，每次從未處理的資料中随機取出一個數字，然後把該數字放在數組的尾部，即數組尾部存放的是已經處理過的數字。

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

在剩下的53張中繼續随機選取一張與第二張牌進行交換

直至最後一張。

時間複雜度為O(n),空間複雜度為O(1),缺點必須知道數組長度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]);
 }
} 
           

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);
}