1。 背景
筆試時，遇到一個演算法題：差不多是 在n個不同的數中隨機取出不重複的m個數。洗牌演算法是將原來的陣列進行打散，使原陣列的某個數在打散後的陣列中的每個位置上等機率的出現，剛好可以解決該問題。
2。 洗牌演算法
由抽牌、換牌和插牌衍生出三種洗牌演算法，其中抽牌和換牌分別對應Fisher-Yates Shuffle和Knuth-Durstenfeld Shhuffle演算法。
2。1 Fisher-Yates Shuffle演算法
最早提出這個洗牌方法的是 Ronald A。 Fisher 和 Frank Yates，即 Fisher–Yates Shuffle，其基本思想就是從原始陣列中隨機取一個之前沒取過的數字到新的陣列中，具體如下：
1。 初始化原始陣列和新陣列，原始陣列長度為n（已知）；
2。 從還沒處理的陣列（假如還剩k個）中，隨機產生一個［0， k）之間的數字p（假設陣列從0開始）；
3。 從剩下的k個數中把第p個數取出；
4。 重複步驟2和3直到數字全部取完；
5。 從步驟3取出的數字序列便是一個打亂了的數列。
下面證明其隨機性，即每個元素被放置在新陣列中的第i個位置是1/n（假設陣列大小是n）。
證明：一個元素m被放入第i個位置的機率P = 前i-1個位置選擇元素時沒有選中m的機率 * 第i個位置選中m的機率，即
時間複雜度為O（n*n），空間複雜度為O（n）。
2。2 Knuth-Durstenfeld Shuffle
Knuth 和 Durstenfeld 在Fisher 等人的基礎上對演算法進行了改進，在原始陣列上對數字進行互動，省去了額外O（n）的空間。該演算法的基本思想和 Fisher 類似，每次從未處理的資料中隨機取出一個數字，然後把該數字放在陣列的尾部，即陣列尾部存放的是已經處理過的數字。
演算法步驟為：
1。 建立一個數組大小為 n 的陣列 arr，分別存放 1 到 n 的數值；
2。 生成一個從 0 到 n - 1 的隨機數 x；
3。 輸出 arr 下標為 x 的數值，即為第一個隨機數；
4。 將 arr 的尾元素和下標為 x 的元素互換；
5。 同2，生成一個從 0 到 n - 2 的隨機數 x；
6。 輸出 arr 下標為 x 的數值，為第二個隨機數；
7。 將 arr 的倒數第二個元素和下標為 x 的元素互換；
……
如上，直到輸出 m 個數為止
該演算法是經典洗牌演算法。它的proof如下：
對於arr［i］，洗牌後在第n-1個位置的機率是1/n（第一次交換的隨機數為i）
在n-2個位置機率是［（n-1）/n］ * ［1/（n-1）］ = 1/n，（第一次交換的隨機數不為i，第二次為arr［i］所在的位置（注意，若i=n-1，第一交換arr［n-1］會被換到一個隨機的位置））
在第n-k個位置的機率是［（n-1）/n］ * ［（n-2）/（n-1）］ *。。。* ［（n-k+1）/（n-k+2）］ *［1/（n-k+1）］ = 1/n
（第一個隨機數不要為i，第二次不為arr［i］所在的位置（隨著交換有可能會變）……第n-k次為arr［i］所在的位置）。
時間複雜度為O（n），空間複雜度為O（1），缺點必須知道陣列長度n。
原始陣列被修改了，這是一個原地打亂順序的演算法，演算法時間複雜度也從Fisher演算法的 O（n2）提升到了O（n）。由於是從後往前掃描，無法處理不知道長度或動態增長的陣列。
2。3 Inside-Out Algorithm
Knuth-Durstenfeld Shuffle 是一個內部打亂的演算法，演算法完成後原始資料被直接打亂，儘管這個方法可以節省空間，但在有些應用中可能需要保留原始資料，所以需要另外開闢一個數組來儲存生成的新序列。
Inside-Out Algorithm 演算法的基本思思是從前向後掃描資料，把位置i的資料隨機插入到前i個（包括第i個）位置中（假設為k），這個操作是在新陣列中進行，然後把原始資料中位置k的數字替換新陣列位置i的數字。其實效果相當於新陣列中位置k和位置i的數字進行互動。
如果知道arr的lengh的話，可以改為for迴圈，由於是從前往後遍歷，所以可以應對arr［］數目未知的情況，或者arr［］是一個動態增加的情況。
證明如下：
原陣列的第 i 個元素（隨機到的數）在新陣列的前 i 個位置的機率都是：（1/i） * ［i/（i+1）］ * ［（i+1）/（i+2）］ *。。。* ［（n-1）/n］ = 1/n，（即第i次剛好隨機放到了該位置，在後面的n-i 次選擇中該數字不被選中）。
原陣列的第 i 個元素（隨機到的數）在新陣列的 i+1 （包括i + 1）以後的位置（假設是第k個位置）的機率是：（1/k） * ［k/（k+1）］ * ［（k+1）/（k+2）］ *。。。* ［（n-1）/n］ = 1/n（即第k次剛好隨機放到了該位置，在後面的n-k次選擇中該數字不被選中）。
時間複雜度為O（n），空間複雜度為O（n）。
2。4 蓄水池抽樣
從N個元素中隨機等機率取出k個元素，N長度未知。它能夠在o（n）時間內對n個數據進行等機率隨機抽取。如果資料集合的量特別大或者還在增長（相當於未知資料集合總量），該演算法依然可以等機率抽樣。
虛擬碼：
上述虛擬碼的意思是：先選中第1到k個元素，作為被選中的元素。然後依次對第k+1至第N個元素做如下操作：
每個元素都有k/x的機率被選中，然後等機率的（1/k）替換掉被選中的元素。其中x是元素的序號。
proof：
每次都是以 k/i 的機率來選擇
例： k=1000的話， 從1001開始作選擇，1001被選中的機率是1000/1001，1002被選中的機率是1000/1002，與我們直覺是相符的。
接下來證明：
假設當前是i+1， 按照我們的規定，i+1這個元素被選中的機率是k/i+1，也即第 i+1 這個元素在蓄水池中出現的機率是k/i+1
此時考慮前i個元素，如果前i個元素出現在蓄水池中的機率都是k/i+1的話，說明我們的演算法是沒有問題的。
對這個問題可以用歸納法來證明：k < i <=N
1。當i=k+1的時候，蓄水池的容量為k，第k+1個元素被選擇的機率明顯為k/（k+1）， 此時前k個元素出現在蓄水池的機率為 k/（k+1）， 很明顯結論成立。
2。假設當 j=i 的時候結論成立，此時以 k/i 的機率來選擇第i個元素，前i-1個元素出現在蓄水池的機率都為k/i。
證明當j=i+1的情況：
即需要證明當以 k/i+1 的機率來選擇第i+1個元素的時候，此時任一前i個元素出現在蓄水池的機率都為k/（i+1）。
前i個元素出現在蓄水池的機率有2部分組成， ①在第i+1次選擇前得出現在蓄水池中，②得保證第i+1次選擇的時候不被替換掉
①。由2知道在第i+1次選擇前，任一前i個元素出現在蓄水池的機率都為k/i
②。考慮被替換的機率：
首先要被替換得第 i+1 個元素被選中（不然不用替換了）機率為 k/i+1，其次是因為隨機替換的池子中k個元素中任意一個，所以不幸被替換的機率是 1/k，故
前i個元素（池中元素）中任一被替換的機率 = k/（i+1） * 1/k = 1/i+1
則（池中元素中）沒有被替換的機率為： 1 - 1/（i+1） = i/i+1
綜合① ②，透過乘法規則
得到前i個元素出現在蓄水池的機率為 k/i * i/（i+1） = k/i+1
故證明成立
如果m被選中，則隨機替換水庫中的一個物件。最終每個物件被選中的機率均為k/n，證明如下：
證明：第m個物件被選中的機率=選擇m的機率*（其後元素不被選擇的機率+其後元素被選擇的機率*不替換第m個物件的機率），即
因此，蓄水池抽樣因為不需知道n的長度，可用於機器學習的資料集的劃分，等機率隨機抽樣分為測試集和訓練集。
————————————————
原文連結：https：//blog。csdn。net/qq_26399665/java/article/details/79831490
