/ 算法  

如何打乱数组? (洗牌算法)

定义问题

既然要让计算机打乱数组,我们得先定义下“打乱”是什么?

让一个数组内的元素随机排列

 

那么,你怎么定义 随机

要知道在计算机软件层面只能通过各种算法产生伪随机数,真正的随机必须结合物理和硬件来实现,比如可以根据周围电磁场的噪音生成之类

 

所以稍稍修改下目标:

让一个数组内的元素随机排列,并且每种排列结果尽可能少偏差

制定方案

我们有那些随机打乱数组的算法呢?

1. sort + random

1
arr.sort(function() {return .5 - Math.random()});

运行结果 ↓
(橙色正偏差,紫色负偏差,全部接近白灰最佳)

从结果看来这种算法并不好,究其原因,各浏览器 sort 的实现为了追求效率,并不会每两个元素都能进行比较和置换,那么可能性的分布就已经很不均了。

2. map + sort + random

1
2
3
4
var random = array.map(Math.random);
array.sort(function(a, b) {
return random[a] - random[b];
})

在上面的方案上做改进,创建等长度的随机数组,再根据随机数组排序原数组。从结果上看还不错。

运行结果 ↓
(橙色正偏差,紫色负偏差,全部接近白灰最佳)

3. Fisher–Yates shuffle

经典的洗牌算法,lodash 库 中的 _.shuffle 正是用的这个算法。

思路: 将第 i 位与 0 至 n-i 中随意(random)一位置换位置

1
2
3
4
5
6
7
8
9
function shuffle(array) {
var m = array.length, t, i;
while (m) {
i = Math.floor(Math.random() * m--);
t = array[m];
array[m] = array[i];
array[i] = t;
}
}

运行结果 ↓
(橙色正偏差,紫色负偏差,全部接近白灰最佳)




应该还有很多方案,欢迎讨论呀~