大家好，我是IT修真院武汉分院第11期的学员，一枚正直纯洁善良的前端程序员，今天给大家分享一下，修真院官网js任务2，深度思考中的知识点——洗牌算法具体指的是什么？
1.背景介绍
洗牌算法，顾名思义，它的产生是用来解决类似洗牌这种场景的问题的，目的是产生一串等概率的随机列，使得很难去预测牌的顺序，洗牌算法是我们常见的随机问题，在玩游戏，随机排序时经常用到。同时它也是一道经典的面试题。
2.知识剖析
何为洗牌算法？
一个1到n的序列，随机打乱，保证每个数出现在任意一个位置的概率相同。
3.常见问题
有哪些实现洗牌的算法？
4.解决方案
Fisher-Yates Shuffle链接
一般化方法
假如要洗牌，那么最随机的做法无疑是从牌堆里随便抽一张出来，然后放在一边，之后从剩下的牌里重复之前的操作，直到所有牌都被抽出来放到了另一堆中。抽象到代码世界，按相同的做法，就是随机从数组里取出一个元素，保存到另一个数组，然后重复之，直到原数组中所有元素都处理掉。
缺点：即使一个序号上的元素已经被处理过了，由于随机函数产生的数是随机的，所有这个被处理过的元素序号可能在之后的循环中不断出现。
改进方法
处理完一个元素后，我们用Array的splice()方法将其从目标数组中移除同时也更新了目标数组的长度，如此一来下次遍历的时候是从新的长度开始，不会重复处理的情况了。
缺点：因为调用splice来删除数组元素会导致删除位置之后的所有元素要做shift操作来向前补充，从而达到将数组长度减小的目的，当然这是在后台自动完成的，但这无疑增加了算法的复杂度。
算法能否再次优化？
考虑不创建新的数组来保存已经抽取的元素:随机从数组中抽出一个元素，然后与最后个元素交换，相当于把这个随机抽取的元素放到了数组最后面去，表示它已经是被随机过了，同时被换走的那个元素跑到前面去了，会在后续的重复操作中被随机掉。一轮操作过后，下一轮我们只在剩下的n-1个元素也就是数组的前n-1个元素中进行相同的操作，直到进行到第一个。
5.编码实战
6.扩展思考
除了洗牌算法，还有哪些经典的排序算法？
7.参考文献
参考一：由乱序播放说开了去-数组的打乱算法Fisher–Yates Shuffle
参考二：UC面试题-完美洗牌算法
8.更多讨论
1，什么是好的洗牌算法？
洗牌之后，如果能够保证每一个数出现在所有位置上的概率是相等的，那么这种算法是符合要求的；这在个前提下，尽量降低时间和空间复杂度。
2，洗牌中抽牌法指的是什么？
每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。
function shuffle_pick_1(m) //洗牌 //抽牌法
{
//生成m张牌
var arr = new Array(m);
for (var i=0; i
arr[i] = i;
}
//每次抽出一张牌，放在另一堆。因为要在数组里抽出元素，把后面的所有元素向前拉一位，所以很耗时。
var arr2 = new Array();
for (var i=m; i>0; i--) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}
3，洗牌中换牌法指的是什么？
第i张与任意一张牌换位子，换完一轮即可。
function shuffle_swap(m) //洗牌 //换牌法
{
//生成m张牌
var arr = new Array(m);
for (var i=0; i
arr[i] = i;
}
//第i张与任意一张牌换位子，换完一轮即可
for (var i=0; i
var rnd = Math.floor(Math.random()*(i+1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}
感谢大家观看
今天的分享就到这里啦，欢迎大家点赞、转发、留言、拍砖~
网友评论