[導讀]有一次參加面試，面試官問我：“會玩牌吧？” 內心：“咋滴，這是要玩德州撲克（或者炸金花），贏了他就能通過面試么？” 結果…… 沒想到面試官的下一句話：“給我講講洗牌算法以及它的應用場景吧！” 哈哈，以上內容純屬虛構背景這確實也是一道面試題，我

有一次參加面試，面試官問我：“會玩牌吧？”

內心：“咋滴，這是要玩德州撲克（或者炸金花），贏了他就能通過面試么？”

結果……

沒想到面試官的下一句話：“給我講講洗牌算法以及它的應用場景吧！”

背景

這確實也是一道面試題，我曾經(jīng)多次面試中都有遇到這個題目或者這個題目的變種。

你不妨花 1 秒，想想？

什么是洗牌算法

從名字上來看，就是給你一副牌讓你洗唄，用怎樣的方法才能洗得均勻呢？請大佬表演一下。

其實洗牌算法就是一種隨機算法，你在斗地主的時候，隨機把牌的順序打亂就行。一個足夠好的洗牌算法最終結果應該是可以讓牌的順序足夠隨機。好像有點繞~

這么來說吧，一副牌大家斗地主的話用 54 張（不考慮你們打配配牌的情形哈），那么這 54 張牌的順序的話，按照排列組合算法，應該是有 54! 這么多種，然后你的洗牌算法就是從這 54! 種排列中，隨機選 1 種。

無聊的石頭算了一下，54 的階乘有多大呢？大概就是這么大一長串數(shù)字，2308436973392413804720927448683027581083278564571807941132288000000000000L，準確答案看下圖：

我們還是以 4 張牌作為例子吧。

4 張牌，JQKA，所有的排列有 4!=4*3*2*1=24 種，分別如下：

('J', 'Q', 'K', 'A')
('J', 'Q', 'A', 'K')
('J', 'K', 'Q', 'A')
('J', 'K', 'A', 'Q')
('J', 'A', 'Q', 'K')
('J', 'A', 'K', 'Q')
('Q', 'J', 'K', 'A')
('Q', 'J', 'A', 'K')
('Q', 'K', 'J', 'A')
('Q', 'K', 'A', 'J')
('Q', 'A', 'J', 'K')
('Q', 'A', 'K', 'J')
('K', 'J', 'Q', 'A')
('K', 'J', 'A', 'Q')
('K', 'Q', 'J', 'A')
('K', 'Q', 'A', 'J')
('K', 'A', 'J', 'Q')
('K', 'A', 'Q', 'J')
('A', 'J', 'Q', 'K')
('A', 'J', 'K', 'Q')
('A', 'Q', 'J', 'K')
('A', 'Q', 'K', 'J')
('A', 'K', 'J', 'Q')
('A', 'K', 'Q', 'J')

那么，一個均勻的洗牌算法，就是每次洗牌完后，獲得上面每種順序的概率是相等的，都等于1/24。感覺已經(jīng)出來了一種算法了，那就是先像前文所述把所有的排列情況都枚舉出來，分別標上號 1-24 號，然后從 24 中隨機取一個數(shù)字（先不考慮如何能做到隨機取了，這個話題好像也沒那么容易），獲取其中這個數(shù)字對應的號的排列。

這個算法復雜度是多少？假設為 N 張牌的話，應該就是 1/N!（注意是階乘，這里可不是感嘆號），顯然復雜度太高了。

有沒有更好的方法呢？答案當然是肯定的。

經(jīng)典的洗牌算法

洗牌算法實際上是一個很經(jīng)典的算法，在經(jīng)典書籍《算法導論》里面很靠前的部分就有講解和分析。

我們把這個洗牌過程用更加“程序員”的語言描述一下，就是假設有一個 n 個元素的數(shù)組 Array[n]，通過某種方式，隨機產(chǎn)生一個另外一個序列Array'[n]讓數(shù)組的每個元素 Array[i] 在數(shù)組中的每個位置出現(xiàn)的概率都是1/n。

其實方法可以這樣，依次從 Array 中隨機選擇 1 個，依次放到 Array' 中即可。證明一下：

Array[0]，在新數(shù)組的第 0 個位置處的概率為： 1/n，因為隨機選，只能是 1/n的概率能選中；
Array[1]，在新數(shù)組的第 1 個位置處的概率為： 1/n，因為第一次沒選中 Array[1]的概率為 n-1/n，再結合第二次（只剩下n-1個了，所以分母為 n-1）選中的概率為： 1/n-1，因此概率為：。
依此類推，可以證明前述問題。

其實，我們也可以不用另外找個數(shù)組來存結果，Array'也可以理解為還是前面的這個 Array，只不過里面元素的順序變化了。

這其實可以理解為一個 “排序”（其實是亂序）過程，算法如下：

void shuffle(List list) {
  int n = list.size();
  for (int i = 0; i < n; i++) {
    int j = random(i, n); // 隨機產(chǎn)生 [i, n) 中的一個數(shù)，每個概率一致
    // list 中第 i 個元素和 第 j 個元素互換位置 
    swap(list[i], list[j]);
  }
}

接下來是如何證明呢？不能你說隨機就隨機吧，你說等概率就等概率吧。下面還是跟著石頭哥一起來看看如何證明吧（這也是面試中的考察點）。

我們假設經(jīng)過排序后，某個元素 Array[x] 恰好排在位置 x 處的概率為，則該元素恰好排在第 x 處的概率是前 x-1 次時都沒有被隨機到，并且第 x 次時，恰好 random(x, n) = x了。

還是在循環(huán)中列舉幾項，更好理解一些（寫完，才發(fā)現(xiàn)跟前面的解釋差不多）：

i = 0, random(0, n) 沒有返回 x，共 n 個數(shù)，肯定返回了其他 n-1 個中的一個，因此概率為
i = 1, ramdom(1, n) 沒有返回 x，共 n - 1 個數(shù)，肯定返回了其他 n-2 個中的一個，即該為
依此類推……
i = x-1, random(x-1, n) 沒有返回 x，共 n - (x-1) 個數(shù)，肯定返回了其他 n-(x-1)-1 個中的一個，即為
i = x， random(x, n) 恰好返回了 x，共 n-x 個數(shù)，概率為

因此，到這算是簡單證明了任何元素出現(xiàn)在任何位置的概率是相等的。

注意說明一下，這是理論上的值，概率類的問題在量不大的情況下很有可能有隨機性的。就像翻硬幣，正反面理論上的值都是一半一半的，但你不能說一定是正反面按照次序輪著來。

看看 JDK 中的實現(xiàn)

我們還是來看看 JDK 中的實現(xiàn)。JDK 中 Collections 中有如下的實現(xiàn)方法 shuffle：

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    // 石頭備注：本機特定版本中的常量 SHUFFLE_THRESHOLD=5
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();
        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

基本上能看懂大概，不過是不是看看源碼還是能獲得新技能的。

上面條件分支大概分兩類：

如果是數(shù)組類型，就是可以 O(1)隨機訪問的List；或者傳入的 list 小于 SHUFFLE_THRESHOLD。
否則的話不能隨機訪問的鏈表類型，則花 O(n) 轉成數(shù)組，再 shuffle，最后又回滾回鏈表。轉成數(shù)組的目的很簡單，可以快速定位某個下標的元素。

第一步的這個 SHUFFLE_THRESHOLD 其實就是一個經(jīng)驗調優(yōu)值，即便假設不能通過快速下標定位某個元素（即需要遍歷的方式定位），當輸入的 size 比較小的時候，和先花 O(n)轉成數(shù)組最后又轉回成鏈表相比，也能有更快的速度。

另外多說一句，其實這種參數(shù)化調優(yōu)方式在各種語言實現(xiàn)的時候很常見的，比如你去看排序算法的實現(xiàn)中，比如 Java 中 Arrays.sort 就是用的 DualPivotQuicksort（源碼在java.util.DualPivotQuicksort中），里面實現(xiàn)邏輯中，當數(shù)組大小較小時也是用的其他如的插入排序，如下圖所示。

洗牌算法的應用

肝到凌晨 2 點了，明天繼續(xù)寫吧....

回到本篇標題說的應用場景上來，比如開篇提到的 Eureka 注冊中心的 Client 就是通過把server 的 IPList 打亂順序，然后挨個取來實現(xiàn)理論上的均勻的負載均衡。

代碼（在 github: Netflix/eureka 中，公眾號就不單獨貼出來了）在這里com.netflix.discovery.shared.resolver.ResolverUtils?？创a如下，是不是跟前文的算法差不多？（具體寫法不一樣而已）

public static <T extends EurekaEndpoint> List<T> randomize(List<T> list) {
    List<T> randomList = new ArrayList<>(list);
    if (randomList.size() < 2) {
        return randomList;
    }
    Random random = new Random(LOCAL_IPV4_ADDRESS.hashCode());
    int last = randomList.size() - 1;
    for (int i = 0; i < last; i++) {
        int pos = random.nextInt(randomList.size() - i);
        if (pos != i) {
            Collections.swap(randomList, i, pos);
        }
    }
    return randomList;
}