x洗牌演算法

A. C語言 洗牌演算法

/*洗牌程序:用任何語言,隨機分配52張撲克牌到52個位置上,每個位置只容許放一張牌
用1-13表示紅心A--K
14-26表示黑桃A,2,3-,Q,K
27-39表示方塊A,2,3-,Q,K
40-52表示黑桃A,2,3-,Q,K
也就是生成1-52不重復的隨機數，放到數組中*/

#include<iomanip.h>
#include<stdlib.h>
#include<time.h>

const int N=52;
static int a[N];

int create(int n)
{
return (1+rand()%52);
}

int main()
{
int i,j;
srand(time(0));
for(i=0;i<N;++i)
{
a[i]=create(N);
for(j=0;j<i;++j)
{
if(a[j]==a[i])
{
a[i]=(a[i]+1)%52;
}
}
cout<<setw(5)<<a[i];
}
cout<<endl;
return 0;
}

B. 隨機洗牌：哪一種演算法是正確的

幾乎所有的程序員都寫過類似於「洗牌」的演算法，也就是將一個數組隨機打亂後輸出，雖然很簡單，但是深入研究起來，這個小小的演算法也是大有講究。我在面試程序員的時候，就會經常讓他們當場寫一個洗牌的函數，從中可以觀察到他們對於這個問題的理解和寫程序的基本功。 在深入討論之前，必須先定義出一個基本概念：究竟洗牌演算法的本質是什麼？也就是說，什麼樣的洗牌結果是「正確」的？ 雲風曾經有一篇博文，專門討論了這個問題，他也給出了一個比較確切的定義，在經過洗牌函數後，如果能夠保證每一個數據出現在所有位置的概率是相等的，那麼這種演算法是符合要求的。在這個前提下，盡量降低時間復雜度和空間復雜度就能得到好的演算法。 第一個洗牌演算法：隨機抽出一張牌，檢查這張牌是否被抽取過，如果已經被抽取過，則重新抽取，直到找到沒被抽出過的牌，然後把這張牌放入洗好的隊列中，重復該過程，直到所有的牌被抽出。 大概是比較符合大腦對於洗牌的直觀思維，這個演算法經常出現在我遇到的面試結果中，雖然它符合我們對於洗牌演算法的基本要求，但這個演算法並不好，首先它的復雜度為O(N2)，而且需要額外的內存空間保存已經被抽出的牌的索引。所以當數據量比較大時，會極大降低效率。