洗牌算法在實際應用中使用的比較廣泛，比如抽獎、三國殺游戲等等。由于要完全理解洗牌算法存在一定的難度，所以洗牌算法也經常被拿來做算法筆試題。例如以下兩個常見的筆試題：在n個不同的數中隨機取出不重復的m個數；打亂一副撲克牌，不能用額外空間，證明為什么是隨機的？

在平時開發中，我們經常會用到隨機數，而我們一般要生成隨機數時，都是使用Random類實現。然而Random 類實現的隨機數是真正的隨機數嗎？Java中的Random又是如何實現隨機數的生成呢？

Random是通過一個種子通過一定的算法來獲取的隨機數，實現的算法有很多，在Java的Random類中的算法如下：

public int nextInt() {return next(32); }protected int next(int bits) {long oldseed, nextseed;AtomicLong seed = this.seed;do {oldseed = seed.get();nextseed = (oldseed * multiplier + addend) & mask;} while (!seed.compareAndSet(oldseed, nextseed));return (int)(nextseed >>> (48 - bits)); }

如果種子一樣，產生的隨機數也是一樣的，這種計算隨機數不滿足隨機性，所以我們把Random生成的隨機數通常稱為偽隨機數。通常隨機數是無法預先計算出來的，并且每個數字出現的概率是一樣的。隨機數必須滿足以下兩個條件：

• 不可計算性，即在隨機數產生前，不能通過任何方式計算出來。
• 機會均等性，即需要保證每個數出現的概率是相等的。

在平常生活中，通過擲骰子的方式就可以很容易獲取一個隨機數。但在計算機中，要生成一個隨機數，卻不是一件簡單的事。首先，我們需要考慮在一定范圍內如何隨機

• Fisher-Yates Shuffle洗牌算法

假設我們有一個數組a[1,2,3]，我們需要實現一個算法，將順序的1,2,3隨機的打亂在數組中。而這里的隨機是表示每個數最終落在每個位置的概率都需要是一樣的。我們可以通過隨機抽取數組，之后將抽取的數放入到另一個數組的位置的方式來實現隨機打亂數組，例如，

新數組的第一個位置抽取1的概率為1/3（1/n），而抽取不到1的概率為2/3(n-1/n)；

當第一個位置抽取到了1，第二個位置抽取2的概率為1/2（在第二步的概率，不是整個過程的概率），那么在整個過程中第二個位置抽取到數字2的概率是第一個位置抽取不到數字2的概率*第二個位置抽到到數字2的概率，即2/3*1/2=1/3，即(n-1/n)*(1/n-1)=1/n；

依次類推，在前面兩個抽取為數字1,2時，在新數組第三個位置被抽到3的概率為1，而第一步和第二步抽取不到3的概率分別為2/3、1/2，所以整個過程中第三個位置抽取到數字3的概率為第一個位置抽取不到數字3的概率*第二個位置抽取不到數字3的概率*第三個位置抽到到數字3的概率，即2/3*1/2*1=1/3，即(n-1/n)*(1/n-1)*1=1/n。

依次類推，一個元素m被放入第i個位置的概率P = 前i-1個位置選擇元素時沒有選中m的概率 * 第i個位置選中m的概率，即

在 i = 0 的情況下，很顯然p=1/n。對于 i > 0 的情況，前一個式子的分子正好能把下一個式子的分母約去，到最后也只有第一個式子分母還在。因此，不管是哪一輪摸到了哪一個數，概率都是1/n ，所以這個數組的每個排列組合都是等概率的。

以上這種類似抽牌來實現的洗牌算法，這個算法是由兩個科學家 Fisher 和 Yates提出的，所以人們稱之為Fisher-Yates Shuffle算法。我們可以通過Java來實現一份Fisher-Yates Shuffle算法打亂一份撲克牌的代碼：

private Random rand = new Random(); private String[] b; public static void shuffle(String[] a) {int n = a.length;for (int i = 0; i < n; i++){ // Exchange a[i] with random element in a[i..N-1]int r = rand.nextInt(n-i);String temp = a[r];b[i] = temp;a.remove(temp);} }

Fisher-Yates Shuffle算法的時間復雜度是O（n），空間復雜度是O（n）。

• Knuth-Durstenfeld 洗牌算法

Fisher-Yates Shuffle算法的特點是通過隨機抽取的方式來實現的，這種洗牌方式的缺點就是需要額外的空間來存儲隨機抽取的數字，那有沒有一種算法可以省去額外的存儲空間呢？

Knuth 和 Durstenfeld 在Fisher-Yates Shuffle算法研究的基礎上對洗牌算法進行了改進，通過將隨機抽取的數字與在原來數組上的數字進行交換，這樣就省去了額外的空間，降低了空間復雜度。

private Random rand = new Random(); public static void shuffle(String[] a) {int n = a.length;for (int i = 0; i < n; i++){ // Exchange a[i] with random element in a[i..N-1]int r = rand.nextInt(n-i);String temp = a[i];a[i] = a[r];a[r] = temp;} }

這樣洗牌算法的時間復雜度是O（n），而空間復雜度是O（1）。

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的c++随机打乱数组_【洗牌算法】你确定这样的抽奖算法是随机的？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。