当前位置：首页 > article >正文

【Unity/C#】Fisher-Yates洗牌算法

article 2025/1/1 3:44:40

在进行某些类型的游戏设计中，常常需要将某些元素进行打乱。比如，扑克牌的打乱、生成随机的元素序列等等。那么推荐你使用下面这种打乱效果优良的算法——Fisher-Yates洗牌算法。

它的思路非常简单：

1.已知一段要进行打乱的数组

2.创建一个新的数组，每次从要打乱的数组中随机选择一个元素，加入到新数组当中

3.从原来的数组中移除这个元素

4.直到原来的数组的元素全部被移除完，即打乱完毕。

那么我们来实现一下这个效果：

public List<int> Shuffle(List<int> a)
{
    List<int> b = new List<int>();
    for(int i = 0 ; i < a.Count ; i++)
    {
        int index = Random.Range(0,a.Count)
        int item = a[index];
        b.Add(item);
        a.RemoveAt(index);
    }
    return b;
}

上述这个是按照算法的思路来进行实现的，然而时间复杂度还可以进行优化。

我们可以直接将原本的数组进行改造，能够将时间复杂度减低到O(n)

我们来看看优化版本的算法：

public List<int> Shuffle(List<int> a)
{
    //获得列表的长度
    int n = a.Count;
    for(int i = n - 1 ; i > 0 ; i--)
    {
        //随机选一个索引，
        int index = Random.Range(0,i + 1);
        //将随机抽取到的元素与当前元素做交换
        (a[index],a[i]) = (a[i],a[index]);
    }
    return a;
}

查看全文

http://www.kler.cn/a/456851.html