洗牌算法的一種實現(xiàn)

作者：fuqcool 發(fā)布時間：2011-04-17 23:16:02 分類： algorithms

最近自己在做一個小的程序，需要把一個集合里面的元素全部隨機地打散。自己想了一個方法，復雜度是n，覺得不太快。后來參照了一下python關(guān)于shuffle的算法，發(fā)現(xiàn)我的方法跟它的是一樣的，連python的代碼都這么寫，可能已經(jīng)沒有辦法再快了吧！

下面就來介紹洗牌算法，用C語言描述。

算法的前提是有一個產(chǎn)生隨機數(shù)的函數(shù)

// Generates a random integer between beg and end.
int GetRandomNumber(int beg, int end);

還有一個交換函數(shù)。

// Swap a and b.
void Swap(int a, int b);

上面兩個函數(shù)我就不寫出實現(xiàn)了，因為這篇文章的重點在于算法的討論。

假設我們有一堆撲克牌，怎么才能把這副牌完全打亂呢？計算機當然不能像人手那樣洗牌。但是它可以產(chǎn)生隨機數(shù)，隨機地從一副牌中抽出一張牌是可以的。既然這樣那就好辦了，我們不停地從牌堆中隨機抽取一張撲克牌，然后把這些牌堆起來，直到原來的牌堆只剩下一張牌的時候為止。這樣不就完成了洗牌的動作了嗎。

下面是C代碼：

int Shuffle(int[] a, int len)
{
    for (int i = len - 1; i > 0; i--)
    {
        // Select an element from index 0 to i randomly;
        int index = GetRandomNumber(0, i);
        // exchange a[i] with a[index]
        Swap(a[index], a[i]);
    }
}

順便也貼出python的random單元關(guān)于shuffle的實現(xiàn)：

def shuffle(self, x, random=None, int=int):
    """x, random=random.random -> shuffle list x in place; return None.

    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.
    """

    if random is None:
        random = self.random
    for i in reversed(xrange(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = int(random() * (i+1))
        x[i], x[j] = x[j], x[i]