如何真正的打乱数组?
1
2
| let arr = [1, 2, 3]
arr.sort(() => Math.random() - 0.5)
|
上述代码看似可以打乱，但是不是真正的打乱。做下测试：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| const RandomShuffle = (arr) => {
return arr.sort(() => Math.random() - 0.5)
}
const testResult = () => {
let times = 100000
let res = {}
for (let i = 0; i < times; i++) {
let arr = [1, 2, 3]
RandomShuffle(arr)
let key = JSON.stringify(arr)
res[key] ? res[key]++ : (res[key] = 1)
}
for (let key in res) {
res[key] = (res[key] / times) * 100 + '%'
}
console.log(res)
}
testResult()
[1,2,3]: "37.66%"
[2,1,3]: "12.57%"
[1,3,2]: "6.109%"
[3,1,2]: "6.343999999999999%"
[2,3,1]: "6.22%"
[3,2,1]: "31.097%"
|
可以看出末尾数字是 3 的概率为 50%，而不是想象中的 33%。原因是因为 sort 函数底层是使用插入排序实现的。所以初始为[1,2,3]的时候，插入排序从 2 开始，和前面做比较，此时有 50%的几率顺序 50%的几率逆序，所以[1,2,3][2,1,3]出现几率都为 50%。接下来的操作如下图所示：
Knuth-Durstenfeld 洗牌算法
1
2
3
4
5
6
7
8
| const KnuthDurstenfeldShuffle = arr => {
for (let i = arr.length - 1; i >= 0; i--) {
let randomIndex = Math.floor(Math.random() * (i + 1))
;[arr[i], arr[randomIndex]] = [arr[randomIndex], arr[i]]
}
return arr
}
|
思路：
- 选取数组(长度 n)中最后一个元素(arr[length-1])，将其与 n 个元素中的任意一个交换，此时最后一个元素已经确定
- 选取倒数第二个元素(arr[length-2])，将其与 n-1 个元素中的任意一个交换
- 重复第 1 2 步，直到剩下 1 个元素为止
Fisher-Yates 洗牌算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
const FisherYatesShuffle = arr => {
let result = [];
while (arr.length > 0) {
let randomIndex = Math.floor(Math.random() * arr.length)
result.push(arr[randomIndex])
arr.splice(randomIndex, 1)
}
return result
}
[1,2,3]: "16.646%"
[1,3,2]: "16.633%"
[2,1,3]: "16.55%"
[2,3,1]: "16.787%"
[3,1,2]: "16.662%"
[3,2,1]: "16.722%"
|
思路：
- 从还没处理的数组（假如还剩 n 个）中，产生一个[0, n]之间的随机数 random
- 从剩下的 n 个元素中把第 random 个元素取出到新数组中
- 删除原数组第 random 个元素
- 重复第 2 3 步直到所有元素取完
- 最终返回一个新的打乱的数组
参考资料
洗牌算法
如何测试洗牌程序
洗牌算法(shuffle)的 js 实现
