高效洗牌算法介绍

发表于

最近写了一个梭哈牌戏Demo，简单介绍用到的洗牌算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void shuffle()
{
	// 随机位数索引
	int tmpIndex;
	// 临时存储数组当前值
	Card tmpCard;
	for (int i = 0; i < CardDeck.DECK_SIZE; i++)
	{
		tmpIndex = (int)(Math.random() * CardDeck.DECK_SIZE);
		if (tmpIndex != i)
		{
			tmpCard = cards[tmpIndex];
			cards[tmpIndex] = cards[i];
			cards[i] = tmpCard;
		}
	}
	return;
}

思想：从数组第一位开始，随机random一个数字，第一位和随机出的那位交换；然后依次遍历这个过程到最后一张牌。时间复杂度O(n)，空间复杂度O(1)。
优点：与抽牌算法（随机抽牌放到新数组，直到抽完为止）相比，当前洗牌算法随机性更强，已随机的位数仍会与后面随机的数位交换；无需开辟新数组，空间复杂度降低。

另外，Demo与传统梭哈相比，加入五张鬼牌，难度升级。
牌型判断及简单机器博弈算法还是有点难度的。感兴趣可看下Demo：Github链接