方法一：隨機生成法

首先，我介紹一種很常見的方法：隨機生成法（我自己命名的），這方法我在掃雷游戲中隨機分布雷的位置時用過（思想是一樣的），該方法要點就是從頭開始逐個隨機生成規(guī)定區(qū)域的數(shù)字，如果新生成隨機數(shù)之前已經(jīng)生成過就不保存該數(shù)；如果新生成的隨機數(shù)之前沒有生成過就保存該數(shù)；直到生成的數(shù)字的數(shù)量達到所需的數(shù)量。

實現(xiàn)代碼如下：

size_t shuffle(char s[], int n) 
{ 
    size_t t=0;//計算循環(huán)次數(shù) 
    int c=0; 
    while(c<n) 
    { 
        t++; 
        int num = rand()%n; 
        if (memchr(s,num,c) == NULL) 
        { 
            s[c++] = static_cast<char>(num); 
        } 
    } 
    return t; 
} 
 
 
void printCards(char s[], int n) 
{ 
    for (int i=0; i<n; i++) 
    { 
        cout << static_cast<int>(s[i]) << " "; 
    } 
    cout << endl; 
} 

代碼中使用了memchr函數(shù)（時間復雜度可能是O(n)，沒找到依據(jù)），即使是O(1)，它的循環(huán)生成隨機數(shù)的次數(shù)是不固定的（大于等于需要生成的個數(shù)）。

方法二：交換位置法

這種方法是我昨天在參加騰訊筆試考試時候想到的，今天回到學校后在寢室測試了一番，基本思路是：先初始化一串分布的數(shù)字，然后為每個位置依次生成一個與之交換的隨機位置，如果生成的隨機位置不是它本身就執(zhí)行交換操作。

實現(xiàn)代碼：

void swap(int& a, int& b) 
{ 
    a = a^b; 
    b = a^b; 
    a = a^b; 
} 
 
size_t shuffle2(int s[], int n) 
{ 
    size_t t=0;//計算循環(huán)次數(shù) 
    for (int i=0; i<n; i++) 
    { 
        t++; 
        s[i] = i; 
    } 
    for (int i=0; i<n; i++) 
    { 
        t++; 
        int num = rand()%n; 
        if (num != i) 
        { 
            swap(s[num],s[i]); 
        } 
    } 
    return t; 
} 
 
void printCards2(int s[], int n) 
{ 
    for (int i=0; i<n; i++) 
    { 
        cout << s[i] << " "; 
    } 
    cout << endl; 
} 

比較：在時間上方法二比方法一快好多，因為交換位置的次數(shù)的***值是限定了的（生成隨機數(shù)的次數(shù)是固定的），而且省去了查找新生成數(shù)是否在已生成數(shù)中的時間。方法一中，當新生成的數(shù)在已生成的數(shù)中就需要從新生成一個隨機數(shù)，從而隨機生成數(shù)的次數(shù)是不固定的（有最小值）。

測試代碼：

結果：

我還是不能確定第二種方法是不是更好的，因為是自己想到的，我的驗證也不是很完善，也許有什么其他的缺點（比如說隨機性太弱），也沒在其他書上看到過，如果網(wǎng)友們在哪看到過就告訴下我吧，方法一是在《c和c++代碼精粹》中文版P97中找到的。

后續(xù)補充：

謝謝chncwang的回復，方法二不是完全隨機的，完全隨機的修改如下：

size_t shuffle22(int s[], int n) 
{ 
    size_t t=0;//計算循環(huán)次數(shù) 
    for (int i=0; i<n; i++) 
    { 
        t++; 
        s[i] = i; 
    } 
    for (int i=n-1; i>0; --i) 
    { 
        t++; 
        int num = rand()%(i+1); 
        if (num != i) 
        { 
            swap(s[num],s[i]); 
        } 
    } 
    return t; 
} 

使用標準庫<algorithm>中的random_shuffle()函數(shù)實現(xiàn)很簡單，代碼如下：

int main() 
{ 
    vector<int> s_stl; 
    for (int i=0; i<CARDS_COUNT; ++i) s_stl.push_back(i); 
    random_shuffle(s_stl.begin(),s_stl.end()); 
    cout << "使用C++算法庫："; 
    for (vector<int>::iterator it=s_stl.begin(); it!=s_stl.end(); ++it) 
        cout << " " << *it; 
    return 0; 
} 

原文鏈接：http://www.cnblogs.com/hanxi/archive/2012/10/15/2725047.html

【編輯推薦】