好些月前，前同事突然考我一个题目：怎么把一副牌打乱？
洗牌，说到底不就是数组元素打乱么？不假思索，我的第一想法就是，另起数组，然后通过随机数把原数组中元素一项一项的拿到新数组中。然而，稍微细想一番，这样子做的话肯定不是优解，其中一个瓶颈部分就在于，每次提取一个元素以后，我们都需要重新计算原始数组的剩余元素和长度，这明显会带来挺大的性能消耗。由此引发对洗牌程序的兴趣和学习。
# 洗牌准则
- 足够乱。
- 必定要有
n!个结果。这个很好理解，假设有n个数，最后的排列结果必定有n!个。
# 思路
从低位 0 开始， 原始数组长度结束，进行遍历。每一个步骤都进行以下的操作：
- 获取从当前下标到数组最后值下标的随机整数。
- 交换当前下标和已得随机下标的值。
# 上代码
// 随机函数，或者 [min,max]中的任意整数
function randomIndex (min, max) {
max += 1
return Math.floor(Math.random() * (max - min) + min)
}
// 洗牌函数
function shuffle (sourceArr) {
const len = sourceArr.length
for (let i = 0; i < len; i ++) {
const rand = randomIndex(i, len - 1)
if(rand === i) continue
const item = sourceArr[rand]
sourceArr[rand] = sourceArr[i]
sourceArr[i] = item
}
return sourceArr
}
console.log(shuffle([1,2,3,4,5,6,7,8,9,10]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
其中，主要代码实现如下：
- 实现了一个
randomIndex函数，主要负责返回从min到max中的随机整数。 - 实现一个
shuffle洗牌程序， 内部逻辑就是获取从当前i到 最后元素下标的随机整数，然后对换i和 大于等于i的随机整数下标的值。直到遍历结束，确保所有的值都对换过。
# 对应准则
因为每次都是使用
Math.random来随机获取下标值的，因此满足了足够乱的需求。由于每次对换的时候，
shuffle中，与第i(下标) 个元素对换的元素都有length - i个可能，因此满足n!的需求。
# 效果
由于本例是 javaScript 代码编写，因此代码可以直接放在浏览器控制台来查看结果。这里简单的验证一下：
# 总结
- 洗牌算法两大要求：一是要足够乱，二是结果集数量上是
n!。 - 洗牌算法实现非常简单，基本思路就是遍历所有元素，通过当前元素与剩余随机下标（包含当前下标）的元素进行对换来完成。