相信你對於演算法有了一點認識，如果今天要求您將一組牌進行洗牌的動作，該怎麼做?
Fisher-Yates 洗牌演算法
Fisher-Yates 洗牌算法是從 最後一個數開始隨機選擇並交換，其用意是為了公平的打亂，使得每種組合的機率相等，且能夠保證 O(N) 的時間複雜度。
O(N)簡單介紹
O(N) 代表 「線性時間（Linear Time）」，表示演算法的執行時間與輸入大小 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）
i = 4（最後一個元素5）- 在
[0, 4]中選擇j = 2 - 交換
array[4]和array[2]
索引: 0 1 2 3 4
數字: [1, 2, 5, 4, 3]
第二輪（i = 3，隨機選擇 j = 1）
i = 3（元素4）- 在
[0, 3]中選擇j = 1 - 交換
array[3]和array[1]
索引: 0 1 2 3 4
數字: [1, 4, 5, 2, 3]
第三輪（i = 2，隨機選擇 j = 2）
i = 2（元素5）- 在
[0, 2]中選擇j = 2 - 因為
j = i，不交換
索引: 0 1 2 3 4
數字: [1, 4, 5, 2, 3]
- （這一步 i = j，所以不變）
第四輪（i = 1，隨機選擇 j = 0）
i = 1（元素4）- 在
[0, 1]中選擇j = 0 - 交換
array[1]和array[0]
索引: 0 1 2 3 4
數字: [4, 1, 5, 2, 3]
完成洗牌！
最終結果（每次執行可能不同）：
[4, 1, 5, 2, 3]
