幾乎所有的程序員都寫(xiě)過(guò)類似于“洗牌”的算法，也就是將一個(gè)數(shù)組隨機(jī)打亂后輸出，雖然很簡(jiǎn)單，但是深入研究起來(lái)，這個(gè)小小的算法也是大有講究。我在面試程序員的時(shí)候，就會(huì)經(jīng)常讓他們當(dāng)場(chǎng)寫(xiě)一個(gè)洗牌的函數(shù)，從中可以觀察到他們對(duì)于這個(gè)問(wèn)題的理解和寫(xiě)程序的基本功。
在深入討論之前，必須先定義出一個(gè)基本概念：究竟洗牌算法的本質(zhì)是什么？也就是說(shuō)，什么樣的洗牌結(jié)果是“正確”的？
云風(fēng)曾經(jīng)有一篇博文，專門(mén)討論了這個(gè)問(wèn)題，他也給出了一個(gè)比較確切的定義，在經(jīng)過(guò)洗牌函數(shù)后，如果能夠保證每一個(gè)數(shù)據(jù)出現(xiàn)在所有位置的概率是相等的，那么這種算法是符合要求的。在這個(gè)前提下，盡量降低時(shí)間復(fù)雜度和空間復(fù)雜度就能得到好的算法。
第一個(gè)洗牌算法：
隨機(jī)抽出一張牌，檢查這張牌是否被抽取過(guò)，如果已經(jīng)被抽取過(guò)，則重新抽取，直到找到?jīng)]被抽出過(guò)的牌，然后把這張牌放入洗好的隊(duì)列中，重復(fù)該過(guò)程，直到所有的牌被抽出。
大概是比較符合大腦對(duì)于洗牌的直觀思維，這個(gè)算法經(jīng)常出現(xiàn)在我遇到的面試結(jié)果中，雖然它符合我們對(duì)于洗牌算法的基本要求，但這個(gè)算法并不好，首先它的復(fù)雜度為O(N2)，而且需要額外的內(nèi)存空間保存已經(jīng)被抽出的牌的索引。所以當(dāng)數(shù)據(jù)量比較大時(shí)，會(huì)極大降低效率。
第二個(gè)算法：
設(shè)牌的張數(shù)為n，首先準(zhǔn)備n個(gè)不容易碰撞的隨機(jī)數(shù)，然后進(jìn)行排序，通過(guò)排序可以得到一個(gè)打亂次序的序列，按照這個(gè)序列將牌打亂。
這也是一個(gè)符合要求的算法，但是同樣需要額外的存儲(chǔ)空間，在復(fù)雜度上也會(huì)取決于所采用的排序算法，所以仍然不是一個(gè)好的算法。
第三個(gè)算法：
每次隨機(jī)抽出兩張牌交換，重復(fù)交換一定次數(shù)次后結(jié)束
void shuffle(int* data, int length)
{
for(int i=0; i<SWAP_COUNTS; i++)
{
//Rand(min, max)返回[min, max)區(qū)間內(nèi)的隨機(jī)數(shù)
int index1 = Rand(0, length);
int index2 = Rand(0, length);
std::swap(data[index1], data[index2]);
}
}
這又是一個(gè)常見(jiàn)的洗牌方法，比較有意思的問(wèn)題是其中的“交換次數(shù)”，我們?cè)撊绾未_定一個(gè)合適的交換次數(shù)？簡(jiǎn)單的計(jì)算，交換m次后，具體某張牌始終沒(méi)有被抽到的概率為((n-2)/n)^m，如果我們要求這個(gè)概率小于1/1000,那么m>-3*ln(10)/ln(1-2/n),對(duì)于52張牌，這個(gè)數(shù)大約是176次，需要注意的是，這是滿足“具體某張牌”始終沒(méi)有被抽到的概率，如果需要滿足“任意一張牌”沒(méi)被抽到的概率小于1/1000，需要的次數(shù)還要大一些，但這個(gè)概率計(jì)算起來(lái)比較復(fù)雜，有興趣的朋友可以試一下。
Update: 這個(gè)概率是
，推算過(guò)程可以參考這里，根據(jù)這個(gè)概率，需要交換280次才能符合要求
第四個(gè)算法：
從第一張牌開(kāi)始，將每張牌和隨機(jī)的一張牌進(jìn)行交換
void shuffle(int* data, int length)
{
for(int i=0; i<length; i++)
{
int index = Rand(0, length);
std::swap(data[i], data[index]);
}
}
很明顯，這個(gè)算法是符合我們先前的要求的，時(shí)間復(fù)雜度為O(N)，而且也不需要額外的臨時(shí)空間，似乎我們找到了最優(yōu)的算法，然而事實(shí)并非如此，看下一個(gè)算法。
第五個(gè)算法：
void shuffle(int* data, int length)
{
for(int i=1; i<length; i++)
{
int index = Rand(0, i);
std::swap(data[i], data[index]);
}
}
一個(gè)有意思的情況出現(xiàn)了，這個(gè)算法和第三種算法非常相似，從直覺(jué)來(lái)說(shuō)，似乎使數(shù)據(jù)“雜亂”的能力還要弱于第三種，但事實(shí)上，這種算法要強(qiáng)于第三種。要想嚴(yán)格的證明這一點(diǎn)并不容易，需要一些數(shù)學(xué)功底，有興趣的朋友可以參照一下這篇論文，或者matrix67大牛的博文，也可以這樣簡(jiǎn)單理解一下，對(duì)于n張牌的數(shù)據(jù)，實(shí)際排列的可能情況為n! 種，但第四種算法能夠產(chǎn)生n^n種排列，遠(yuǎn)遠(yuǎn)大于實(shí)際的排列情況，而且n^n不能被n!整除，所以經(jīng)過(guò)算法四所定義的牌與牌之間的交換程序，很可能一張牌被換來(lái)?yè)Q去又被換回到原來(lái)的位置，所以這個(gè)算法不是最優(yōu)的。而算法五輸出的可能組合恰好是n!種，所以這個(gè)算法才是完美的。
事情并沒(méi)有結(jié)束，如果真的要找一個(gè)最優(yōu)的算法，還是請(qǐng)出最終的冠軍吧！
第六個(gè)算法：
void shuffle(int* data, int length)
{
std::random_shuffle(data, data+length);
}
沒(méi)錯(cuò)，用c++的標(biāo)準(zhǔn)庫(kù)函數(shù)才是最優(yōu)方案，事實(shí)上，std::random_shuffle在實(shí)現(xiàn)上也是采取了第四種方法，看來(lái)還是那句話，“不要重復(fù)制造輪子”