【游戏算法】 - 洗牌算法-Fisher-Yates

Fisher-Yates

Fisher-Yates 洗牌算法（又称为 Knuth 洗牌算法）是一种经典的随机排列算法，能够确保所有可能的排列结果等概率出现，且时间复杂度为，空间复杂度为。

算法原理

Fisher-Yates 洗牌算法的核心思想是通过原地交换元素的方式，从后往前逐步确定每个元素的最终位置。其核心步骤如下：

从数组的最后一个元素开始遍历（索引为）。
生成一个随机索引 ，范围为（其中是当前处理的索引）。
交换当前元素与随机索引的位置。
重复步骤 2~3，直到处理完第一个元素（索引为 0）。

代码实现

#include <algorithm>
#include <random>
#include <vector>

void fisherYatesShuffle(std::vector<int>& arr) {
    std::random_device rd;
    std::mt19937 g(rd());
    
    for (size_t i = arr.size() - 1; i > 0; --i) {
        std::uniform_int_distribution<size_t> dist(0, i);
        size_t j = dist(g);
        std::swap(arr[i], arr[j]);
    }
}

using System;

public class ShuffleAlgorithm {
    public static void FisherYatesShuffle(int[] array) {
        Random random = new Random();
        for (int i = array.Length - 1; i > 0; i--) {
            int j = random.Next(0, i + 1); // [0, i]
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

function fisherYatesShuffle<T>(array: T[]): void {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1)); // [0, i]
        [array[i], array[j]] = [array[j], array[i]];
    }
}

function fisher_yates_shuffle(array)
    math.randomseed(os.time())
    for i = #array, 2, -1 do
        local j = math.random(1, i) -- Lua随机数范围[1,i]
        array[i], array[j] = array[j], array[i]
    end
end