有一次參加面試，面試官問(wèn)我：“會(huì)玩牌吧？”

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

結(jié)果……

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

背景

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

你不妨花 1 秒，想想？

什么是洗牌算法

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

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

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

無(wú)聊的石頭算了一下，54 的階乘有多大呢？大概就是這么大一長(zhǎng)串?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')

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

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

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

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

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

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

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

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

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

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

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) 中的一個(gè)數(shù)，每個(gè)概率一致
    // list 中第 i 個(gè)元素和 第 j 個(gè)元素互換位置 
    swap(list[i], list[j]);
  }
}

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

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

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

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

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

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

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

我們還是來(lái)看看 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]);
        }
    }
}

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

上面條件分支大概分兩類(lèi)：

• 如果是數(shù)組類(lèi)型，就是可以 O(1)隨機(jī)訪(fǎng)問(wèn)的List；或者傳入的 list 小于 SHUFFLE_THRESHOLD。
• 否則的話(huà)不能隨機(jī)訪(fǎng)問(wèn)的鏈表類(lèi)型，則花 O(n) 轉(zhuǎn)成數(shù)組，再 shuffle，最后又回滾回鏈表。轉(zhuǎn)成數(shù)組的目的很簡(jiǎn)單，可以快速定位某個(gè)下標(biāo)的元素。

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

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

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

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

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

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

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í)，在任何需要打亂順序的場(chǎng)景里面都可以用這個(gè)算法，舉個(gè)例子，播放器一般都有隨機(jī)播放的功能，比如你自己有個(gè)歌單 list，但想隨機(jī)播放里面的歌曲，就也可以用這個(gè)方法來(lái)實(shí)現(xiàn)。

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

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

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

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

題目 1

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

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

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

題目 2

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

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