大家好，又见面了，我是你们的朋友全栈君。
一副扑克54张牌，有54!种排列方式。最佳的洗牌算法，应该能够等概率地生成这54!种结果中的一种
基于Unity的洗牌算法代码实现
抽牌洗牌
原理
这是完全合乎现实洗牌逻辑的算法。
就是抽出纸牌的最后一张随机插入到牌库中，这般抽54次就完成了对扑克牌的洗牌
复杂度
空间O（1），时间O（n^2)
优缺点
如果牌库是以一个数组描述，这种插入式的洗牌不可避免地要大量移动元素。
Fisher_Yates算法
原理
取两个列表，一个是洗牌前的序列A{1,2….54)，一个用来放洗牌后的序列B，B初始为空
while A不为空
随机从A取一张牌加入B末尾
复杂度
空间O（n），时间O（n^2)
代码实现
1 List<int> list = new List<int>(pukes.pukes);//洗牌前的序列A 2 List<int> newlist = new List<int>(list.Count);//洗牌后的序列B 3 for(int i = 0 ; i < pukes.pukes.Length ; ++i) 4 { 5 int randomIndex = Random.Range(0, list.Count); 6 int r = list[randomIndex];//随机取牌 7 newlist.Add(r); 8 list.RemoveAt(randomIndex); 9 } 10 pukes.ResetPuke(newlist.ToArray());//序列B为洗牌后的结果
优缺点
算法原理清晰，但额外开辟了一个List，而且为List删除元素是不可避免地需要移动元素
通过54次生成的随机数取1/54,1/53,…1/1能等概率地生成这54!种结果中的一种
Knuth_Durstenfeld算法
Knuth 和Durstenfeld 在Fisher 等人的基础上对算法进行了改进。 每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部， 即数组尾部存放的是已经处理过的数字 。 这是一个原地打乱顺序的算法，算法时间复杂度也从Fisher算法的 O ( n 2 )提升到了 O ( n )。
1 for(int i = pukes.pukes.Length - 1;i>0;--i) 2 { 3 int randomIndex = Random.Range(0, i+1); 4 pukes.Swap(randomIndex, i); 5 }
是最佳的洗牌算法
Inside_Out算法
C++ stl中random_shuffle使用的就是这种算法
原理
在[0, i]之间随机一个下标j，然后用位置j的元素替换掉位置i的数字
通过54次生成的随机数取1/1,1/2,…1/54能等概率地生成这54!种结果中的一种
复杂度
空间O（1），时间O（n)
代码实现
1 public static void Shuffle(Pukes pukes) 2 { 3 int len = pukes.pukes.Length; 4 for (int i = 0; i < len; ++i) 5 { 6 int randomIndex = Random.Range(0, i + 1); 7 pukes.Swap(i, randomIndex); 8 } 9 }
random_shuffle
关于c++ stl 的random_shuffle
它的算法原理和Knuth_Durstenfeld类似
先从所有元素中选一个与位置1的元素交换，然后再从剩下的n-1个元素中选择一个放到位置2，以此类推
参考链接
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/155556.html原文链接：https://javaforall.net
