Fisher-Yates 洗牌演算法

相信你對於演算法有了一點認識，如果今天要求您將一組牌進行洗牌的動作，該怎麼做?

Fisher-Yates 洗牌演算法

Fisher-Yates 洗牌算法是從 最後一個數開始隨機選擇並交換，其用意是為了公平的打亂，使得每種組合的機率相等，且能夠保證 O(N) 的時間複雜度。

O(N)簡單介紹

簡單來說：當 N 增加，執行時間也會以相同比例增加。

• N = 10，執行大約 10 次
• N = 100，執行大約 100 次

這邊要特別提醒一點，通常程式步驟的時間複雜度會是用程式執行會碰到的最壞狀況 (Worst Case) 來表示。

也因此，當我們要從 n 個櫃子中找到特定的目標，最慘的情況需要花剛好 n 個步驟才能找到，我們就會說此搜尋的時間複雜度為 O(n)。

O(N) 與其他複雜度的比較

好，回到主題，我們來分析一下程式碼的思維。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 函數生成一組隨機排序的唯一數字
void generateRandomUniqueNumbers(int arr[], int size) {
    // 步驟 1：初始化陣列，依序填入從 1 到 size 的數字
    for (int i = 0; i < size; i++) {
        arr[i] = i + 1; // 將每個元素賦予從 1 到 size 的唯一數值
    }

    // 步驟 2：使用 Fisher-Yates 演算法將陣列隨機打亂
    for (int i = size - 1; i > 0; i--) {  // 從陣列尾部開始向前迭代
        // 生成一個介於 0 和 i 之間的隨機索引 j
        int j = rand() % (i + 1);

        // 交換索引 i 和 j 的元素
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // 到此為止，arr 包含了從 1 到 size 的數字並隨機排列
}

int main() {
    int n;

    // 步驟 1：詢問用戶需要生成的唯一隨機整數數量
    printf("Enter the number of unique random integers (excluding 0): ");
    scanf("%d", &n);

    // 步驟 2：宣告一個陣列來儲存唯一隨機數字
    int arr[n];

    // 步驟 3：將隨機數生成器的種子設為當前時間
    srand(time(0));

    // 步驟 4：生成隨機唯一數字
    generateRandomUniqueNumbers(arr, n);

    // 步驟 5：輸出隨機排序的唯一整數
    printf("Random unique integers:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);  // 輸出陣列中的每個數字
    }
    printf("\n"); // 打印完所有數字後換行

    return 0;
}

• Fisher-Yates 洗牌演算法步驟
• • 從最後一個元素開始，選擇 i = N-1（索引從 4 開始）。
  • 在 [0, i] 區間內選擇一個隨機索引 j，並與 array[i] 交換。
  • 縮小範圍 i--，繼續隨機選取 j，直到 i = 0。

步驟示範

初始陣列：

索引:  0   1   2   3   4
數字:  [1,  2,  3,  4,  5]  // 原始數組

第一輪（i = 4，隨機選擇 j = 2）

1. i = 4（最後一個元素 5）
2. 在 [0, 4] 中選擇 j = 2
3. 交換 array[4] 和 array[2]

索引:  0   1   2   3   4
數字:  [1,  2,  5,  4,  3]

第二輪（i = 3，隨機選擇 j = 1）

1. i = 3（元素 4）
2. 在 [0, 3] 中選擇 j = 1
3. 交換 array[3] 和 array[1]

索引:  0   1   2   3   4
數字:  [1,  4,  5,  2,  3]

第三輪（i = 2，隨機選擇 j = 2）

1. i = 2（元素 5）
2. 在 [0, 2] 中選擇 j = 2
3. 因為 j = i，不交換

索引:  0   1   2   3   4
數字:  [1,  4,  5,  2,  3]

• （這一步 i = j，所以不變）

第四輪（i = 1，隨機選擇 j = 0）

1. i = 1（元素 4）
2. 在 [0, 1] 中選擇 j = 0
3. 交換 array[1] 和 array[0]

索引:  0   1   2   3   4
數字:  [4,  1,  5,  2,  3]

完成洗牌！

最終結果（每次執行可能不同）：

[4, 1, 5, 2, 3]