C语言 随机打乱数组（shuffle array）

1、Fisher-Yates 洗牌算法

Fisher-Yates 洗牌算法是一种经典的高效算法，时间复杂度为 O(n)，可以在数组中随机打乱元素。使用 rand() 函数和交换元素法。

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

void shuffle(int arr[], int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);  // 生成 [0, i] 之间的随机数
        // 交换 arr[i] 和 arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

int main() {
    srand(time(0));  // 设置随机种子

    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    shuffle(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

2、使用 rand() 函数和暴力法

通过两层循环随机交换数组中的元素。虽然它可以工作，但效率较低，时间复杂度为 O(n^2)。

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

void shuffle(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int j = rand() % n;  // 随机生成 0 到 n-1 之间的索引
        // 交换 arr[i] 和 arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

int main() {
    srand(time(0));  // 设置随机种子

    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    shuffle(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

3、使用 rand() 函数和双重交换法

通过两次随机交换来打乱数组。虽然时间复杂度为 O(n)，但相较于 Fisher-Yates 算法来说不太常用。

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

void shuffle(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int j = rand() % n;  // 随机生成索引
        // 交换 arr[i] 和 arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        // 再次随机交换
        int k = rand() % n;
        temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
}

int main() {
    srand(time(0));  // 设置随机种子

    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    shuffle(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}