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

所以我們面臨兩個問題：

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

2. 設計怎樣的算法來打亂數組才能做到「真的亂」？

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

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

一、洗牌算法

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

分析洗牌算法正確性的準則：產生的結果必須有 n! 種可能，否則就是錯誤的。這個很好解釋，因為一個長度為 n 的數組的全排列就有 n! 種，也就是說打亂結果總共有 n! 種。算法必須能夠反映這個事實，才是正確的。

我們先用這個準則分析一下第一種寫法的正確性：

// 假設傳入這樣一個 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)第一輪迭代時，i=0，rand 的取值范圍是 [0,4]，有 5 個可能的取值。

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

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

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

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

所以整個過程產生的所有可能結果仍然有 5*4*3*2=5!=n! 種，因為乘以 1 可有可無嘛。所以這種寫法也是正確的。

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

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

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

現在你應該明白這種寫法為什么會錯誤了。因為這種寫法得到的所有可能結果有 n^n 種，而不是 n! 種，而且 n^n 一般不可能是 n! 的整數倍。

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

后文會講到，概率均等是算法正確的衡量標準，所以這個算法是錯誤的。

二、蒙特卡羅方法驗證正確性

洗牌算法，或者說隨機亂置算法的正確性衡量標準是：對于每種可能的結果出現的概率必須相等，也就是說要足夠隨機。

如果不用數學嚴格證明概率相等，可以用蒙特卡羅方法近似地估計出概率是否相等，結果是否足夠隨機。

記得高中有道數學題：往一個正方形里面隨機打點，這個正方形里緊貼著一個圓，告訴你打點的總數和落在圓里的點的數量，讓你計算圓周率。

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

類似的，我們可以對同一個數組進行一百萬次洗牌，統計各種結果出現的次數，把頻率作為概率，可以很容易看出洗牌算法是否正確。整體思想很簡單，不過實現起來也有些技巧的，下面簡單分析幾種實現思路。

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

每次進行洗牌算法后，就把得到的打亂結果對應的頻數加一，重復進行 100 萬次，如果每種結果出現的總次數差不多，那就說明每種結果出現的概率應該是相等的。寫一下這個思路的偽代碼：

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

是的，不過作為一種驗證方法，我們不需要 n 太大，最多用長度為 5 或 6 的 arr 試下就差不多了吧，因為我們只想比較概率驗證一下正確性而已。

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

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 + ' '); // 頻率

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

另外，細心的讀者可能發(fā)現一個問題，上述兩種思路聲明 arr 的位置不同，一個在 for 循環(huán)里，一個在 for 循環(huán)之外。其實效果都是一樣的，因為我們的算法總要打亂 arr，所以 arr 的元素順序并不重要，只要所含元素不變就行。

三、最后總結

本文第一部分介紹了洗牌算法（隨機亂置算法），通過一個簡單的分析技巧證明了該算法的四種正確形式，并且分析了一種常見的錯誤寫法，相信你一定能夠寫出正確的洗牌算法了。

第二部分寫了洗牌算法正確性的衡量標準，即每種隨機結果出現的概率必須相等。如果我們不用嚴格的數學證明，可以通過蒙特卡羅方法大力出奇跡，粗略驗證算法的正確性。蒙特卡羅方法也有不同的思路，不過要求不必太嚴格，因為我們只是尋求一個簡單的驗證。