我知道大家會(huì)各種花式排序，但是如果叫你打亂一個(gè)數(shù)組，你是否能做到胸有成竹？即便你拍腦袋想出一個(gè)算法，怎么證明你的算法就是正確的呢？亂序算法不像排序算法，結(jié)果唯一可以很容易檢驗(yàn)，因?yàn)椤竵y」可以有很多種，你怎么能證明你的算法是「真的亂」呢？

所以我們面臨兩個(gè)問題：

1. 什么叫做「真的亂」？

2. 設(shè)計(jì)怎樣的算法來打亂數(shù)組才能做到「真的亂」？

這種算法稱為「隨機(jī)亂置算法」或者「洗牌算法」。

本文分兩部分，第一部分詳解最常用的洗牌算法。因?yàn)樵撍惴ǖ募?xì)節(jié)容易出錯(cuò)，且存在好幾種變體，雖有細(xì)微差異但都是正確的，所以本文要介紹一種簡(jiǎn)單的通用思想保證你寫出正確的洗牌算法。第二部分講解使用「蒙特卡羅方法」來檢驗(yàn)我們的打亂結(jié)果是不是真的亂。蒙特卡羅方法的思想不難，但是實(shí)現(xiàn)方式也各有特點(diǎn)的。

一、洗牌算法

此類算法都是靠隨機(jī)選取元素交換來獲取隨機(jī)性，直接看代碼（偽碼），該算法有 4 種形式，都是正確的：

分析洗牌算法正確性的準(zhǔn)則：產(chǎn)生的結(jié)果必須有 n! 種可能，否則就是錯(cuò)誤的。這個(gè)很好解釋，因?yàn)橐粋€(gè)長(zhǎng)度為 n 的數(shù)組的全排列就有 n! 種，也就是說打亂結(jié)果總共有 n! 種。算法必須能夠反映這個(gè)事實(shí)，才是正確的。

我們先用這個(gè)準(zhǔn)則分析一下第一種寫法的正確性：

// 假設(shè)傳入這樣一個(gè) arr
int[] arr = {1,3,5,7,9};

void shuffle(int[] arr) {
    int n = arr.length(); // 5
    for (int i = 0 ; i < n; i++) {
        int rand = randInt(i, n - 1);
        swap(arr[i], arr[rand]);
    }
}

for 循環(huán)第一輪迭代時(shí)，i=0，rand 的取值范圍是 [0,4]，有 5 個(gè)可能的取值。

for 循環(huán)第二輪迭代時(shí)，i=1，rand 的取值范圍是 [1,4]，有 4 個(gè)可能的取值。

后面以此類推，直到最后一次迭代，i=4，rand 的取值范圍是 [4,4]，只有 1 個(gè)可能的取值。

可以看到，整個(gè)過程產(chǎn)生的所有可能結(jié)果有 5*4*3*2*1=5!=n! 種，所以這個(gè)算法是正確的。

分析第二種寫法，前面的迭代都是一樣的，少了一次迭代而已。所以最后一次迭代時(shí) i = 3，rand 的取值范圍是 [3,4]，有 2 個(gè)可能的取值。

所以整個(gè)過程產(chǎn)生的所有可能結(jié)果仍然有 5*4*3*2=5!=n! 種，因?yàn)槌艘?1 可有可無嘛。所以這種寫法也是正確的。

如果以上內(nèi)容你都能理解，那么你就能發(fā)現(xiàn)第三種寫法就是第一種寫法，只是將數(shù)組從后往前迭代而已；第四種寫法是第二種寫法從后往前來。所以它們都是正確的。

如果讀者思考過洗牌算法，可能會(huì)想出如下的算法，但是這種寫法是錯(cuò)誤的：

void shuffle(int[] arr) {
    int n = arr.length();
    for (int i = 0 ; i < n; i++) {
        // 每次都從閉區(qū)間 [0, n-1]
        // 中隨機(jī)選取元素進(jìn)行交換
        int rand = randInt(0, n - 1);
        swap(arr[i], arr[rand]);
    }
}

現(xiàn)在你應(yīng)該明白這種寫法為什么會(huì)錯(cuò)誤了。因?yàn)檫@種寫法得到的所有可能結(jié)果有 n^n 種，而不是 n! 種，而且 n^n 一般不可能是 n! 的整數(shù)倍。

比如說 arr = {1,2,3}，正確的結(jié)果應(yīng)該有 3!=6 種可能，而這種寫法總共有 3^3 = 27 種可能結(jié)果。因?yàn)?27 不能被 6 整除，也就是說總概率不可能被平分，一定有某些情況被「偏袒」了。

后文會(huì)講到，概率均等是算法正確的衡量標(biāo)準(zhǔn)，所以這個(gè)算法是錯(cuò)誤的。

二、蒙特卡羅方法驗(yàn)證正確性

洗牌算法，或者說隨機(jī)亂置算法的正確性衡量標(biāo)準(zhǔn)是：對(duì)于每種可能的結(jié)果出現(xiàn)的概率必須相等，也就是說要足夠隨機(jī)。

如果不用數(shù)學(xué)嚴(yán)格證明概率相等，可以用蒙特卡羅方法近似地估計(jì)出概率是否相等，結(jié)果是否足夠隨機(jī)。

記得高中有道數(shù)學(xué)題：往一個(gè)正方形里面隨機(jī)打點(diǎn)，這個(gè)正方形里緊貼著一個(gè)圓，告訴你打點(diǎn)的總數(shù)和落在圓里的點(diǎn)的數(shù)量，讓你計(jì)算圓周率。

這其實(shí)就是利用了蒙特卡羅方法：當(dāng)打的點(diǎn)足夠多的時(shí)候，點(diǎn)的數(shù)量就可以近似代表圖形的面積。通過面積公式，由正方形和圓的面積比值是可以很容易推出圓周率的。當(dāng)然打的點(diǎn)越多，算出的圓周率越準(zhǔn)確，充分體現(xiàn)了大力出奇跡的真理。

類似的，我們可以對(duì)同一個(gè)數(shù)組進(jìn)行一百萬次洗牌，統(tǒng)計(jì)各種結(jié)果出現(xiàn)的次數(shù)，把頻率作為概率，可以很容易看出洗牌算法是否正確。整體思想很簡(jiǎn)單，不過實(shí)現(xiàn)起來也有些技巧的，下面簡(jiǎn)單分析幾種實(shí)現(xiàn)思路。

第一種思路，我們把數(shù)組 arr 的所有排列組合都列舉出來，做成一個(gè)直方圖（假設(shè) arr = {1,2,3}）：

每次進(jìn)行洗牌算法后，就把得到的打亂結(jié)果對(duì)應(yīng)的頻數(shù)加一，重復(fù)進(jìn)行 100 萬次，如果每種結(jié)果出現(xiàn)的總次數(shù)差不多，那就說明每種結(jié)果出現(xiàn)的概率應(yīng)該是相等的。寫一下這個(gè)思路的偽代碼：

這種檢驗(yàn)方案是可行的，不過可能有讀者會(huì)問，arr 的全部排列有 n! 種（n 為 arr 的長(zhǎng)度），如果 n 比較大，那豈不是空間復(fù)雜度爆炸了？

是的，不過作為一種驗(yàn)證方法，我們不需要 n 太大，最多用長(zhǎng)度為 5 或 6 的 arr 試下就差不多了吧，因?yàn)槲覀冎幌氡容^概率驗(yàn)證一下正確性而已。

第二種思路，可以這樣想，arr 數(shù)組中全都是 0，只有一個(gè) 1。我們對(duì) arr 進(jìn)行 100 萬次打亂，記錄每個(gè)索引位置出現(xiàn) 1 的次數(shù)，如果每個(gè)索引出現(xiàn) 1 的次數(shù)差不多，也可以說明每種打亂結(jié)果的概率是相等的。

void shuffle(int[] arr);

// 蒙特卡羅方法
int N = 1000000;    
int[] arr = {1,0,0,0,0};
int[] count = new int[arr.length];
for (int i = 0; i < N; i++) {
    shuffle(arr); // 打亂 arr
    for (int j = 0; j < arr.length; j++) 
        if (arr[j] == 1) {
            count[j]++;
            break;
        }
}
for (int feq : count) 
    print(feq / N + ' '); // 頻率

這種思路也是可行的，而且避免了階乘級(jí)的空間復(fù)雜度，但是多了嵌套 for 循環(huán)，時(shí)間復(fù)雜度高一點(diǎn)。不過由于我們的測(cè)試數(shù)據(jù)量不會(huì)有多大，這些問題都可以忽略。

另外，細(xì)心的讀者可能發(fā)現(xiàn)一個(gè)問題，上述兩種思路聲明 arr 的位置不同，一個(gè)在 for 循環(huán)里，一個(gè)在 for 循環(huán)之外。其實(shí)效果都是一樣的，因?yàn)槲覀兊乃惴傄騺y arr，所以 arr 的元素順序并不重要，只要所含元素不變就行。

三、最后總結(jié)

本文第一部分介紹了洗牌算法（隨機(jī)亂置算法），通過一個(gè)簡(jiǎn)單的分析技巧證明了該算法的四種正確形式，并且分析了一種常見的錯(cuò)誤寫法，相信你一定能夠?qū)懗稣_的洗牌算法了。

第二部分寫了洗牌算法正確性的衡量標(biāo)準(zhǔn)，即每種隨機(jī)結(jié)果出現(xiàn)的概率必須相等。如果我們不用嚴(yán)格的數(shù)學(xué)證明，可以通過蒙特卡羅方法大力出奇跡，粗略驗(yàn)證算法的正確性。蒙特卡羅方法也有不同的思路，不過要求不必太嚴(yán)格，因?yàn)槲覀冎皇菍で笠粋€(gè)簡(jiǎn)單的驗(yàn)證。