Fisher-Yates 洗牌算法

说明

Fisher-Yates洗牌算法（又称为Knuth洗牌或Durstenfeld洗牌）是一种高效的随机排列算法，能够将一个数组（或列表）中的元素随机打乱。其核心思想是从数组的末尾开始，逐个选取元素，并将其与一个随机位置的元素交换，从而实现打乱的效果。

算法步骤

1. 初始化：从数组的最后一个元素开始，逐一向前处理每个元素。
2. 随机选择位置：对于当前的元素（假设是第i个元素），生成一个在[0, i]区间内的随机数j。
3. 交换元素：将第i个元素与第j个元素交换位置。
4. 继续：重复步骤2和3，直到遍历完数组中的所有元素。

#include <iostream>
#include <vector>
#include <cstdlib>  // for rand()
#include <ctime>    // for time()

void fisherYatesShuffle(std::vector<int>& array) {
    // 获取数组大小
    int n = array.size();
    
    // 遍历数组，从最后一个元素开始
    for (int i = n - 1; i > 0; --i) {
        // 生成一个0到i之间的随机索引
        int j = rand() % (i + 1);
        
        // 交换元素
        std::swap(array[i], array[j]);
    }
}

int main() {
    // 初始化随机数生成器
    srand(static_cast<unsigned int>(time(0)));
    
    // 创建一个数组
    std::vector<int> arr = {1, 2, 3, 4, 5};
    
    // 打印原始数组
    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用Fisher-Yates洗牌
    fisherYatesShuffle(arr);
    
    // 打印打乱后的数组
    std::cout << "Shuffled array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}