方法一：隨機(jī)生成法

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

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

size_t shuffle(char s[], int n) 
{ 
    size_t t=0;//計(jì)算循環(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ù)（時(shí)間復(fù)雜度可能是O(n)，沒(méi)找到依據(jù)），即使是O(1)，它的循環(huán)生成隨機(jī)數(shù)的次數(shù)是不固定的（大于等于需要生成的個(gè)數(shù)）。

方法二：交換位置法

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

實(shí)現(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;//計(jì)算循環(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í)間上方法二比方法一快好多，因?yàn)榻粨Q位置的次數(shù)的***值是限定了的（生成隨機(jī)數(shù)的次數(shù)是固定的），而且省去了查找新生成數(shù)是否在已生成數(shù)中的時(shí)間。方法一中，當(dāng)新生成的數(shù)在已生成的數(shù)中就需要從新生成一個(gè)隨機(jī)數(shù)，從而隨機(jī)生成數(shù)的次數(shù)是不固定的（有最小值）。

測(cè)試代碼：

結(jié)果：

我還是不能確定第二種方法是不是更好的，因?yàn)槭亲约合氲降模业尿?yàn)證也不是很完善，也許有什么其他的缺點(diǎn)（比如說(shuō)隨機(jī)性太弱），也沒(méi)在其他書上看到過(guò)，如果網(wǎng)友們?cè)谀目吹竭^(guò)就告訴下我吧，方法一是在《c和c++代碼精粹》中文版P97中找到的。

后續(xù)補(bǔ)充：

謝謝chncwang的回復(fù)，方法二不是完全隨機(jī)的，完全隨機(jī)的修改如下：

size_t shuffle22(int s[], int n) 
{ 
    size_t t=0;//計(jì)算循環(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; 
} 

使用標(biāo)準(zhǔn)庫(kù)<algorithm>中的random_shuffle()函數(shù)實(shí)現(xiàn)很簡(jiǎ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++算法庫(kù)："; 
    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

【編輯推薦】