本文將講述一個(gè)高效的不重復(fù)隨機(jī)數(shù)列的生成算法，其效率比通常用hashtable 消重的方法要快很多。

首先我們來(lái)看命題：

給定一個(gè)正整數(shù)n，需要輸出一個(gè)長(zhǎng)度為n的數(shù)組，數(shù)組元素是隨機(jī)數(shù)，范圍為0 – n-1，且元素不能重復(fù)。比如 n = 3 時(shí)，需要獲取一個(gè)長(zhǎng)度為3的數(shù)組，元素范圍為0-2，

比如 0,2,1。

這個(gè)問(wèn)題的通常解決方案就是設(shè)計(jì)一個(gè) hashtable ，然后循環(huán)獲取隨機(jī)數(shù)，再到 hashtable 中找，如果hashtable 中沒(méi)有這個(gè)數(shù)，則輸出。下面給出這種算法的代碼

public static int[] GetRandomSequence0(int total)  
{  
    int[] hashtable = new int[total];  
    int[] output = new int[total];  
 
    Random random = new Random();  
    for (int i = 0; i < total; i++)  
    {  
        int num = random.Next(0, total);  
        while (hashtable[num] > 0)  
        {  
            num = random.Next(0, total);  
        }  
 
        output[i] = num;  
        hashtable[num] = 1;  
    }  
 
    return output;  
} 

代碼很簡(jiǎn)單，從 0 到 total - 1 循環(huán)獲取隨機(jī)數(shù)，再去hashtable 中嘗試匹配，如果這個(gè)數(shù)在hashtable中不存在，則輸出，并把這個(gè)數(shù)在hashtable 中置1，否則循環(huán)嘗試獲取隨機(jī)數(shù)，直到找到一個(gè)不在hashtable 中的數(shù)為止。這個(gè)算法的問(wèn)題在于需要不斷嘗試獲取隨機(jī)數(shù)，在hashtable 接近滿時(shí)，這個(gè)嘗試失敗的概率會(huì)越來(lái)越高。

那么有沒(méi)有什么算法，不需要這樣反復(fù)嘗試嗎？答案是肯定的。

 如上圖所示，我們?cè)O(shè)計(jì)一個(gè)順序的數(shù)組，假設(shè)n = 4

***輪，我們?nèi)?0 – 3 之間的隨機(jī)數(shù)，假設(shè)為2，這時(shí)，我們把數(shù)組位置為2的數(shù)取出來(lái)輸出，并把這個(gè)數(shù)從數(shù)組中刪除，這時(shí)這個(gè)數(shù)組變成了

第二輪，我們?cè)偃?0-2 之間的隨機(jī)數(shù)，假設(shè)為1，并把這個(gè)位置的數(shù)輸出，同時(shí)把這個(gè)數(shù)從數(shù)組刪除，以此類推，直到這個(gè)數(shù)組的長(zhǎng)度為0。這時(shí)我們就可以得到一個(gè)隨機(jī)的不重復(fù)的序列。

這個(gè)算法的好處是不需要用一個(gè)hashtable 來(lái)存儲(chǔ)已獲取的數(shù)字，不需要反復(fù)嘗試。算法代碼如下：

public static int[] GetRandomSequence1(int total)  
{  
    List<int> input = new List<int>();  
    for (int i = 0; i < total; i++)  
    {  
        input.Add(i);  
    }  
 
    List<int> output = new List<int>();  
 
    Random random = new Random();  
    int end = total;  
    for (int i = 0; i < total; i++)  
    {  
        int num = random.Next(0, end);  
        output.Add(input[num]);  
        input.RemoveAt(num);  
        end--;  
    }  
 
    return output.ToArray();  
}  

這個(gè)算法把兩個(gè)循環(huán)改成了一個(gè)循環(huán)，算法復(fù)雜度大大降低了，按說(shuō)速度應(yīng)該比***個(gè)算法要快才對(duì)，然而現(xiàn)實(shí)往往超出我們的想象，當(dāng)total = 100000 時(shí)，測(cè)試下來(lái)，***個(gè)算法用時(shí) 44ms, 第二個(gè)用時(shí) 1038 ms ，慢了很多！這是為什么呢？問(wèn)題的關(guān)鍵就在這個(gè) input.RemoveAt 上了，我們知道如果要?jiǎng)h除一個(gè)數(shù)組元素，我們需要把這個(gè)數(shù)組元素后面的所有元素都向前移動(dòng)1，這個(gè)移動(dòng)操作是非常耗時(shí)的，這個(gè)算法慢就慢在這里。到這里，可能有人要說(shuō)了，那我們不用數(shù)組，用鏈表，那刪除不就很快了嗎？沒(méi)錯(cuò)，鏈表是能解決刪除元素的效率問(wèn)題，但查找的速度又大大降低了，無(wú)法像數(shù)組那樣根據(jù)數(shù)組元素下標(biāo)直接定位到元素。所以用鏈表也是不行的。到這里似乎我們已經(jīng)走到了死胡同，難道我們只能用hashtable  反復(fù)嘗試來(lái)做嗎？在看下面內(nèi)容之前，請(qǐng)各位讀者先思考5分鐘。

#p#

…… 思考5分鐘

[[20734]] 

#p#

算法就像一層窗戶紙，隔著窗戶紙，你永遠(yuǎn)無(wú)法知道里面是什么，一旦捅穿，又覺(jué)得非常簡(jiǎn)單。

還是上面那個(gè)例子，假設(shè) n = 4

***輪，我們隨機(jī)獲得2時(shí)，我們不將 2 從數(shù)組中移除，而是將數(shù)組的***一個(gè)元素移動(dòng)到2的位置

 這時(shí)數(shù)組變成了

 第二輪我們對(duì) 0-2 取隨機(jī)數(shù)，這時(shí)數(shù)組可用的***一個(gè)元素位置已經(jīng)變成了2，而不是3。假設(shè)這時(shí)取到隨機(jī)數(shù)為1

我們?cè)侔严聵?biāo)為2 的元素移動(dòng)到下標(biāo)1，這時(shí)數(shù)組變成了

以此類推，直到取出n個(gè)元素為止。

這個(gè)算法的優(yōu)點(diǎn)是不需要用一個(gè)hashtable 來(lái)存儲(chǔ)已獲取的數(shù)字，不需要反復(fù)嘗試，也不用像上一個(gè)算法那樣刪除數(shù)組元素，要做的只是每次把數(shù)組有效位置的***一個(gè)元素移動(dòng)到當(dāng)前位置就可以了，這樣算法的復(fù)雜度就降低為 O(n) ，速度大大提高。

經(jīng)測(cè)試，在 n= 100000 時(shí)，這個(gè)算法的用時(shí)僅為7ms。

下面給出這個(gè)算法的實(shí)現(xiàn)代碼

/// <summary>  
/// Designed by eaglet  
/// </summary>  
/// <param name="total"></param>  
/// <returns></returns>  
public static int[] GetRandomSequence2(int total)  
{  
 
    int[] sequence = new int[total];  
    int[] output = new int[total];  
 
    for (int i = 0; i < total; i++)  
    {  
        sequence[i] = i;  
    }  
 
    Random random = new Random();  
 
    int end = total - 1;  
 
    for (int i = 0; i < total; i++)  
    {  
        int num = random.Next(0, end + 1);  
        output[i] = sequence[num];  
        sequence[num] = sequence[end];  
        end--;  
    }  
 
    return output;  
}  

原文鏈接： http://www.cnblogs.com/eaglet/archive/2011/01/17/1937083.html

【編輯推薦】

1. 為自己做一個(gè)簡(jiǎn)單記賬簿
2. 一步一步設(shè)計(jì)你的數(shù)據(jù)庫(kù)1
3. 數(shù)據(jù)庫(kù)入門級(jí)之算法【一】
4. 數(shù)據(jù)庫(kù)入門級(jí)之算法【二】
5. 數(shù)據(jù)庫(kù)入門級(jí)之算法【三】