发表于： 2019-04-15 20:28:10
1 872
今天完成的事情：今天差不多都在想怎么讲小课堂
明天计划的事情：明天计划讲玩小课堂后去看一看洗牌算法，然后用洗牌算法在写一边JS1
遇到的问题：洗牌算法
1.背景介绍
洗牌算法，顾名思义，它的产生是用来解决类似洗牌这种场景的问题的，目的是产生一串等概率的随机列，使得很难去预测牌的顺序，洗牌算法是我们常见的随机问题，在玩游戏，随机排序时经常用到。同时它也是一道经典的面试题。
2.知识剖析
何为洗牌算法？
一个1到n的序列，随机打乱，保证每个数出现在任意一个位置的概率相同。
3.常见问题
有哪些实现洗牌的算法？
4.解决方案
Fisher-Yates Shuffle链接
一般化方法
假如要洗牌，那么最随机的做法无疑是从牌堆里随便抽一张出来，然后放在一边，之后从剩下的牌里重复之前的操作，直到所有牌都被抽出来放到了另一堆中。抽象到代码世界，按相同的做法，就是随机从数组里取出一个元素，保存到另一个数组，然后重复之，直到原数组中所有元素都处理掉。
缺点：即使一个序号上的元素已经被处理过了，由于随机函数产生的数是随机的，所有这个被处理过的元素序号可能在之后的循环中不断出现。
改进方法
处理完一个元素后，我们用Array的splice()方法将其从目标数组中移除同时也更新了目标数组的长度，如此一来下次遍历的时候是从新的长度开始，不会重复处理的情况了。
缺点：因为调用splice来删除数组元素会导致删除位置之后的所有元素要做shift操作来向前补充，从而达到将数组长度减小的目的，当然这是在后台自动完成的，但这无疑增加了算法的复杂度。
收获：大概了解了洗牌算法，但是还是很蒙逼- -
返回列表
评论