洗牌算法

幾乎所有的程式員都寫過類似于“洗牌”的算法，也就是将一個數組随機打亂後輸出，雖然很簡單，但是深入研究起來，這個小小的算法也是大有講究。我在面試程式員的時候，就會經常讓他們當場寫一個洗牌的函數，從中可以觀察到他們對于這個問題的了解和寫程式的基本功。

    在深入讨論之前，必須先定義出一個基本概念：究竟洗牌算法的本質是什麼？也就是說，什麼樣的洗牌結果是“正确”的？

    雲風曾經有一篇博文，專門讨論了這個問題，他也給出了一個比較确切的定義，在經過洗牌函數後，如果能夠保證每一個資料出現在所有位置的機率是相等的，那麼這種算法是符合要求的。在這個前提下，盡量降低時間複雜度和空間複雜度就能得到好的算法。

    第一個洗牌算法：

随機抽出一張牌，檢查這張牌是否被抽取過，如果已經被抽取過，則重新抽取，直到找到沒被抽出過的牌，然後把這張牌放入洗好的隊列中，重複該過程，直到所有的牌被抽出。

    大概是比較符合大腦對于洗牌的直覺思維，這個算法經常出現在我遇到的面試結果中，雖然它符合我們對于洗牌算法的基本要求，但這個算法并不好，首先它的複雜度為o(n2)，而且需要額外的記憶體空間儲存已經被抽出的牌的索引。是以當資料量比較大時，會極大降低效率。

    第二個算法：

設牌的張數為n，首先準備n個不容易碰撞的随機數，然後進行排序，通過排序可以得到一個打亂次序的序列，按照這個序列将牌打亂。

這也是一個符合要求的算法，但是同樣需要額外的存儲空間，在複雜度上也會取決于所采用的排序算法，是以仍然不是一個好的算法。

    第三個算法：

每次随機抽出兩張牌交換，重複交換一定次數次後結束

void shuffle(int* data, int length)

{

    for(int i=0; i<swap_counts; i++)

    {

        //rand(min, max)傳回[min, max)區間内的随機數

        int index1 = rand(0, length);

        int index2 = rand(0, length);

        std::swap(data[index1], data[index2]);

    }

}

    這又是一個常見的洗牌方法，比較有意思的問題是其中的“交換次數”，我們該如何确定一個合适的交換次數？簡單的計算，交換m次後，具體某張牌始終沒有被抽到的機率為((n-2)/n)^m，如果我們要求這個機率小于1/1000,那麼 m>-3*ln(10)/ln(1-2/n),對于52張牌，這個數大約是176次，需要注意的是，這是滿足“具體某張牌”始終沒有被抽到的機率，如果需要滿足“任意一張牌”沒被抽到的機率小于1/1000，需要的次數還要大一些，但這個機率計算起來比較複雜，有興趣的朋友可以試一下。

    update: 這個機率是

，推算過程可以參考這裡，根據這個機率，需要交換280次才能符合要求

    第四個算法：

從第一張牌開始，将每張牌和随機的一張牌進行交換

    for(int i=0; i<length; i++)

        int index = rand(0, length);

        std::swap(data[i], data[index]);

     }

    很明顯，這個算法是符合我們先前的要求的，時間複雜度為o(n)，而且也不需要額外的臨時空間，似乎我們找到了最優的算法，然而事實并非如此，看下一個算法。

    第五個算法：

    for(int i=1; i<length; i++)

        int index = rand(0, i);

    一個有意思的情況出現了，這個算法和第三種算法非常相似，從直覺來說，似乎使資料“雜亂”的能力還要弱于第三種，但事實上，這種算法要強于第三種。要想嚴格的證明這一點并不容易，需要一些數學功底，有興趣的朋友可以參照一下這篇論文，或者matrix67大牛的博文，也可以這樣簡單了解一下，對于n張牌的資料，實際排列的可能情況為n!

種，但第四種算法能夠産生n^n種排列，遠遠大于實際的排列情況，而且n^n不能被n!整除，是以經過算法四所定義的牌與牌之間的交換程式，很可能一張牌被換來換去又被換回到原來的位置，是以這個算法不是最優的。而算法五輸出的可能組合恰好是n!種，是以這個算法才是完美的。

    事情并沒有結束，如果真的要找一個最優的算法，還是請出最終的冠軍吧！

    第六個算法：

    std::random_shuffle(data, data+length);

    沒錯，用c++的标準庫函數才是最優方案，事實上，std::random_shuffle在實作上也是采取了第四種方法，看來還是那句話，“不要重複制造輪子”