數(shù)據(jù)庫(kù):一個(gè)簡(jiǎn)單有效的洗牌算法

裝配腦袋兄在某個(gè)帖子中指出了一種有意思的洗牌算法，博主按照他的思路寫(xiě)了另外一種洗牌算法。下面是該洗牌算法的思路：
    我們先看一下紙牌游戲。一幅紙牌由 52 張不同的紙牌組成，發(fā)牌時(shí)必須產(chǎn)生不重復(fù)的紙牌，而且洗牌過(guò)程必須公平，即 52! 中紙牌順序應(yīng)該等概率出現(xiàn)。很明顯這種隨機(jī)排列所產(chǎn)生的隨機(jī)數(shù)必須均勻分布且獨(dú)立。由此代碼如下：
    using　System;
    using　System.Diagnostics;
    namespace　Lucifer.CSharp.Sample
    {
    class　Program
    {
    static　void　Main(string[]　args)
    {
    //初始化牌局
    int[]　array　=　new　int[52];
    for　(int　i　=　0;　i　<　array.Length;　i++)
    {
    array[i]　=　i;
    }
    //洗牌
    Permute(array);
    //驗(yàn)證牌局
    for　(int　i　=　0;　i　<　array.Length;　i++)
    {
    var　value　=　array[i];
    for　(int　j　=　0;　j　<　array.Length;　j++)
    {
    if　(j　==　i)　continue;
    Debug.Assert(array[j]　!=　value);
    }
    }
    }
    static　void　Permute(T[]　array)
    {
    Random　random　=　new　Random();
    for　(int　i　=　1;　i　<　array.Length;　i++)
    {
    Swap(array,　i,　random.Next(0,　i));
    }
    }
    static　void　Swap(T[]　array,　int　indexA,　int　indexB)
    {
    T　temp　=　array[indexA];
    array[indexA]　=　array[indexB];
    array[indexB]　=　temp;
    }
    }
    }
    代碼示例中的 Permute(T[] array) 方法產(chǎn)生一個(gè)隨機(jī)序列。第一個(gè)循環(huán)用 1, 2, 3, …, N 初始化該序列。 設(shè)為首頁(yè) 第二個(gè)循環(huán)完成一次隨機(jī)洗牌。在該循環(huán)的每次迭代中，我們講 array[j] 的值于數(shù)組位置在區(qū)間[0, j)之間的某個(gè)元素相交換(也可能不交換)。
    然而，我們要問(wèn)的是 Permute(T[] array) 方法產(chǎn)生的所有排列等概率嗎？
    若根據(jù)該算法，答案為是。因?yàn)橐还灿?N! 種可能的排列，而 Swap(array, i, random.Next(0, i)); 這一句 N-1 次調(diào)用 Next 方法出現(xiàn)的不同結(jié)果也是 N! 種。但是，事實(shí)上答案為否，并非所有排列都是等概率。問(wèn)題就出在可愛(ài)的偽隨機(jī)數(shù)數(shù)生成器(Pseudo-Random Number Generator)上。PRNG 的隨機(jī)性很大程度上限制了隨機(jī)序列的隨機(jī)性。所以，上述代碼需要一個(gè)更好的偽隨機(jī)數(shù)數(shù)生成器以使實(shí)際與理論更加相符。但是好的 PRNG 往往伴隨著性能的下降，比如 Mt19937 隨機(jī)化算法。
    題外話：博主在實(shí)際代碼運(yùn)行中，發(fā)現(xiàn)上述代碼能很好的完成洗牌算法要求，但不保證其能在商業(yè)化項(xiàng)目中得以正確實(shí)踐。我記得云風(fēng)兄在他的博客上也曾經(jīng)討論過(guò)洗牌算法，有興趣的兄弟可以搜索一番