一步步演算法：洗牌演算法詳解與 Fisher-Yates 改進

編輯：關於C語言

撲克牌洗牌是生活常見遊戲，如何用程式實現公平、均勻的隨機排列？C 標準庫的 rand() 產生 0~32767 的偽隨機數，若直接套用會導致嚴重偏差。本文對比兩種常見做法，並引入經典的 Fisher-Yates 洗牌演算法。

方法一：全域交換法（有偏差）

遍歷陣列每個位置 i，隨機選取 0~53 的索引 j 交換：

void shuffle_global(int deck[], int n) {
    for (int i = 0; i < n; i++) {
        int j = rand() % n;           // 關鍵缺陷：範圍固定為 0~n-1
        int tmp = deck[i];
        deck[i] = deck[j];
        deck[j] = tmp;
    }
}

缺點：已洗好的牌會被再次交換，導致排列機率分布不均。對 3 張牌有 3³=27 種等概率路徑，但 3!=6 種排列無法整除 27，必有偏差。

方法二：局部交換法（Fisher-Yates 演算法）

從最後一張牌往前，每次只從「未洗」的區間 [0, i] 抽取：

void shuffle_fisher_yates(int deck[], int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);     // 關鍵修正：範圍縮小為 0~i
        int tmp = deck[i];
        deck[i] = deck[j];
        deck[j] = tmp;
    }
}

優點：

每張牌只被交換一次，時間複雜度 O(n)
產生 n! 種排列機率完全均等（前提是 rand() 均勻）
原地操作，空間複雜度 O(1)

隨機數品質補充

rand() % m 會有模數偏差（modulo bias）。工程上建議：

C++11 使用 std::uniform_int_distribution 搭配 std::mt19937
C 語言可用拒絕採樣：while ((r = rand()) > RAND_MAX - RAND_MAX % m); return r % m;

完整範例程式

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

#define DECK_SIZE 54

void init_deck(int deck[]) {
    for (int i = 0; i < DECK_SIZE; i++) deck[i] = i + 1;
}

void shuffle_fisher_yates(int deck[], int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int tmp = deck[i];
        deck[i] = deck[j];
        deck[j] = tmp;
    }
}

void print_deck(const int deck[]) {
    for (int i = 0; i < DECK_SIZE; i++) {
        printf("%2d ", deck[i]);
        if ((i + 1) % 10 == 0) putchar('\n');
    }
}

int main() {
    srand((unsigned)time(NULL));
    int deck[DECK_SIZE];
    init_deck(deck);
    shuffle_fisher_yates(deck, DECK_SIZE);
    print_deck(deck);
    return 0;
}