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

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

結(jié)果……

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

背景

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

你不妨花 1 秒，想想？

什么是洗牌算法

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

其實(shí)洗牌算法就是一種隨機(jī)算法，你在斗地主的時(shí)候，隨機(jī)把牌的順序打亂就行。一個足夠好的洗牌算法最終結(jié)果應(yīng)該是可以讓牌的順序足夠隨機(jī)。好像有點(diǎn)繞~

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

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

我們還是以 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)出來了一種算法了，那就是先像前文所述把所有的排列情況都枚舉出來，分別標(biāo)上號 1-24 號，然后從 24 中隨機(jī)取一個數(shù)字（先不考慮如何能做到隨機(jī)取了，這個話題好像也沒那么容易），獲取其中這個數(shù)字對應(yīng)的號的排列。

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

有沒有更好的方法呢？答案當(dāng)然是肯定的。

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

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

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

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

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

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

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

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

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

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

還是在循環(huán)中列舉幾項(xiàng)，更好理解一些（寫完，才發(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)在任何位置的概率是相等的。

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

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

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

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    // 石頭備注：本機(jī)特定版本中的常量 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)隨機(jī)訪問的List；或者傳入的 list 小于 SHUFFLE_THRESHOLD。
• 否則的話不能隨機(jī)訪問的鏈表類型，則花 O(n) 轉(zhuǎn)成數(shù)組，再 shuffle，最后又回滾回鏈表。轉(zhuǎn)成數(shù)組的目的很簡單，可以快速定位某個下標(biāo)的元素。

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

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

洗牌算法的應(yīng)用

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

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

代碼（在 github: Netflix/eureka 中，公眾號就不單獨(dú)貼出來了）在這里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;
}

其實(shí)，在任何需要打亂順序的場景里面都可以用這個算法，舉個例子，播放器一般都有隨機(jī)播放的功能，比如你自己有個歌單 list，但想隨機(jī)播放里面的歌曲，就也可以用這個方法來實(shí)現(xiàn)。

還有，就比如名字中的“洗牌”，那些棋牌類的游戲，當(dāng)然會用到名副其實(shí)的“洗牌”算法了。其實(shí)在各種游戲的隨機(jī)場景中應(yīng)該都可以用這個算法的。

擴(kuò)展一下，留道作業(yè)題

跟這個問題類似的，還有一些常見的面試題，本人之前印象中也被問到過（石頭特地去翻了翻當(dāng)年校招等找工作的時(shí)候收集和積累的面試題集）。

以下題目來源于網(wǎng)絡(luò)，因?yàn)槭钱?dāng)初準(zhǔn)備面試時(shí)候收集的，具體來源不詳了。

題目 1

給你一個文本文件，設(shè)計(jì)一個算法隨機(jī)從文本文件中抽取一行，要保證每行被抽取到的概率一樣。

最簡單的思路其實(shí)就是：先把文件每一行讀取出來，假設(shè)有 n 行，這個時(shí)候隨機(jī)從 1-n生成一個數(shù)，讀取對應(yīng)的行即可。

這種方法當(dāng)然可以解決，咱們加深一下難度，假設(shè)文件很大很大很大呢，或者直接要求只能遍歷該文件內(nèi)容一遍，怎么做到呢？

題目 2

其實(shí)題目 1 還可以擴(kuò)展一下，不是選擇 1 行了，是選擇 k 行，又應(yīng)該怎么做呢？

長按訂閱更多精彩▼
如有收獲，點(diǎn)個在看，誠摯感謝