最近需要做一个小游戏，游戏的第一个需求就是要实现一个算法：随机打乱一个数组，也可以称之为洗牌。
现实生活中，洗牌的方式有多种。但对应到计算机实现当中，比较好的一种当属抽牌----不停的从剩下的扑克当中抽取一个，直到抽取的牌组成一副新的扑克为止。这也就是经典的洗牌算法Fisher–Yates shuffle的思路。
简单讲洗牌算法（Fisher–Yates shuffle）是用来将一个有限集合打乱的算法。这个算法生成的随机排列是等概率的，同时需要非常高效。
形象的用图来表示抽牌迭代的过程如下：
| 随机数取值范围 | 随机数 | 原始数据 | 结果 |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 | |||
| 0-7 | 1 | 1 8 3 4 5 6 7 | 2 |
| 0-6 | 4 | 1 8 3 4 7 6 | 5 2 |
| 0-5 | 5 | 1 8 3 4 7 | 6 5 2 |
| 0-4 | 4 | 1 8 3 4 | 7 6 5 2 |
| 0-3 | 1 | 1 4 3 | 8 7 6 5 2 |
| 0-2 | 0 | 3 4 | 1 8 7 6 5 2 |
| 0-1 | 0 | 4 | 3 1 8 7 6 5 2 |
| 0-0 | 0 | 4 3 1 8 7 6 5 2 |
Kotlin实现如下：
fun Array<Int>.shuffle(){
for (i in this.size -1 downTo 0){
var random = Math.floor( Math.random() * (i + 1)).toInt()
var temp = this[random]
this[random] = this[i]
this[i] = temp
}
}
网友评论