1.背景介绍
洗牌算法是我们常见的随机问题，在玩游戏、随机排序时经常会碰到，本质是让一个数组内的元素随机排列。 类似于洗牌，将所有牌的位置打乱，让他们随机出现在任何位置。
2.知识剖析
常见的洗牌算法
方法一：
假如你要洗牌，那么最随机的做法无疑是从牌堆里随便抽一张出来，然后放在一边，之后从剩下的牌里重复之前的操作，直到所有牌都被抽出来放到了另一堆中。抽象到代码世界，按相同的做法，就是随机从数组里取出一个元素，保存到另一个数组，然后重复之，直到原数组中所有元素都处理掉。
function shuffle(array) {
var copy = [],
n = array.length,
i;
// 如果还剩有元素则继续。。。
while (n) {
// 随机抽取一个元素
i = Math.floor(Math.random() * array.length);
// 如果这个元素之前没有被选中过。。
if (i in array) {
copy.push(array[i]);
delete array[i];
n--;
}
}
return copy;
}
方法二：
方法一的问题在此，即使一个序号上的元素已经被处理过了，由于随机函数产生的数是随机的，所有这个被处理过的元素序号可能在之后的循环中不断出现，一是效率问题，另一个就是逻辑问题了，存在一种可能是永远运行不完！
所以改进的做法就是处理完一个元素后，我们用Array的splice()方法将其从目标数组中移除同时也更新了目标数组的长度，如此一来下次遍历的时候是从新的长度开始，不会重复处理的情况了。
function shuffle(array) {
var copy = [],
n = array.length,
i;
// 如果还剩有元素。。 while (n) {
// 随机选取一个元素 i = Math.floor(Math.random() * n--);
// 移动到新数组中 copy.push(array.splice(i, 1)[0]);
}
return copy;
}
最终版：
上面的做法已经可以了，但上面的改进依然还有提升空间。注意到我们要做的仅仅是将数组元素重新排序，已经取出来的元素和剩下的元素之和一定是等于数组原来的总元素个数的。所以可以考虑不创建新的数组来保存已经抽取的元素，可以这样，随机从数组中抽出一个元素，然后与最后个元素交换，相当于把这个随机抽取的元素放到了数组最后面去，表示它已经是被随机过了，同时被换走的那个元素跑到前面去了，会在后续的重复操作中被随机掉。一轮操作过后，下一轮我们只在剩下的n-1个元素也就是数组的前n-1个元素中进行相同的操作，直到进行到第一个。
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length - 1; i >= 0; i--) {
var randomIndex = Math.floor(Math.random() * (i + 1));//获取小于this.length的随机整数 var itemAtIdex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIdex;//input[randomIndex]和input[i]交换值 }
return input;
}
3.常见问题
有没有简洁点的洗牌算法？
4.解决方案
arr.sort(function(){ return 0.5-Math.random()});
结合数组自带的sort()方法编写,中间变量以及值交换什么的都省了,一行代码就可以实现，相对而言比较简单，但是他并不能实现真正意义的随机。
var arr = [0,1,2,3,4,5,6,7,8,9];var res = [0,0,0,0,0,0,0,0,0,0];var t = 10000;for(var i = 0; i < t; i++){
var sorted = shuffle(arr.slice(0));
sorted.forEach(function(o,i){
res[i] += o;
});
}
res = res.map(function(o){
return o / t;
});console.log(res);
5.编码实战
6.扩展思考
怎么保证这个算法得到的数组是完全随机的（即等概）？
计算机本来就没办法实现真正的随机，计算机是一种可确定，可预测的的设备，没法通过一行一行的确定的代码本身自身产生真随机，产生的所谓随机数全部都是伪随机，最多只能做到范围足够大，产生规律足够复杂，感觉像是随机而已。
7.参考文献
参考一： 洗牌算法：给数组随机排序
参考二： 由乱序播放说开了去
参考三： 数组的完全随机排列
8.更多讨论
PPT：https://ptteng.github.io/PPT/PPT-java/Java-1-page.html#/
网友评论