# 洗牌算法
开发中常见将一个数组随机排序(shuffle), 以下是一般写法:
// 0.5: 表示正负 50% 几率
const shuffle = (arr) => arr.sort(() => Math.random() * 0.5)
1
2
2
但是, 这种写法是有问题的, 它并不能真正的打乱数组
中文分析: https://github.com/mqyqingfeng/Blog/issues/51 (opens new window)
总结的原因就是, V8 引擎中针对长短数组使用了不同的排序方法, 短数组使用的是插入排序, 长数组使用了快速排序. 点这里 👉🏻V8源码/Array.prototype.sort (opens new window)
于是乎, 就有大神们弄了一个算法: Fisher–Yates shuffle (opens new window)
点击查看代码
/**
* 洗牌算法
* Fisher–Yates shuffle: <https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle>
* @param {any[]} arr
* @returns {any[]}
*/
const shuffle = (arr) => {
let copyList = arr.splice(0);
let i = copyList.length, j;
while (--i) {
j = Math.floor(Math.random() * i);
[copyList[j], copyList[i]] = [copyList[i], copyList[j]];
}
return copyList;
}
const arr = Array.from({ length : 4 }, (_, index) => ({
id: index,
number: index % 2 + 1
}))
console.log(shuffle(arr))
// [
// {
// id: 3,
// number: 2,
// },
// {
// id: 2,
// number: 1,
// },
// {
// id: 0,
// number: 1,
// },
// {
// id: 1,
// number: 2,
// },
// ]
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43