美文网首页IT修真院-前端修真院
【Js-002】洗牌算法具体指的是什么?

【Js-002】洗牌算法具体指的是什么?

作者: odd4Loah | 来源:发表于2017-12-06 14:26 被阅读19次

    大家好,我是IT修真院北京分院第27期学员,一枚正直善良的前端程序员今天跟大家分享一下洗牌算法的使用。

    今天讲下深度思考中的知识点

    ————洗牌算法具体指的是什么?

    1.背景介绍

    洗牌算法是我们常见的随机问题,在玩游戏、随机排序时经常会碰到,本质是让一个数组内的元素随机排列。

    类似于洗牌,将所有牌的位置打乱,让他们随机出现在任何位置。

    2.知识剖析

    2.1洗牌算法有哪些原理方法

    方法一:

    从牌堆里随便抽一张出来,然后放在一边,之后从剩下的牌里重复之前的操作,直到所有牌都被抽出来放到了另一堆中。抽象到代码世界,按相同的做法,就是随机从数组里取出一个元素,保存到另一个数组,然后重复之,直到原数组中所有元素都处理掉。

    demo-01

    我们创建了一个copy数组,然后遍历目标数组,将其元素复制到copy数组里,同时将该元素从目标数组中删除,这样下次遍历的时候就可以跳过这个序号。

    方法二:

    随机从数组中抽出一个元素,然后与最后个元素交换,相当于把这个随机抽取的元素放到了数组最后面去,表示它已经是被随机过了,同时被换走的那个元素跑到前面去了,会在后续的重复操作中被随机掉。一轮操作过后,下一轮我们只在剩下的n-1个元素也就是数组的前n-1个元素中进行相同的操作,直到进行到第一个。

    demo-02

    shuffle 函数挂载在 Array 对象的原型之下,便于数组直接调用该函数。 在 shuffle 函数内部,this 引用的就是调用该 shuffle 的数组。 用一个新的变量引用 this,也就是调用 shuffle 函数的数组。 接下来的for循环用于遍历所有数组内的所有元素,并进行随机交换。 注意,遍历顺序是从后往前进行的,也就是说从 input.length-1 位置的元素开始,直到遍历到数组中的第一个元素。 遍历过程中的位置由变量 i 指定。 接下来,使用了两行代码在指定范围内挑选一个随机元素。 变量 j 存储了一个随机数,该随机数可以用作数组的索引,进而提取一个随机元素。 注意,该随机数的最大值并不是数组的长度,而是变量i的值。 确定了随机元素的索引之后,用新的变量保存该元素的值,然后交换选中元素和随机元素的值。

    3.常见问题

    洗牌算法是否真的实现了完全随机?

    4.解决方案

    5.扩展思考

    还有什么比较实用的乱序方法?

    虽然sort()不是一个很好的选择,但是也可以实现随机

    6.参考文献

    参考一:洗牌算法:给数组随机排序

    参考二:由乱序播放说开了去

    参考三:当随机不够随机:一个在线扑克游戏的教训

    参考四:随机问题之--洗牌算法

    7.更多讨论

    sort()方法只能在原数组上排序,不是很方便。


    计算机的random方法都是伪随机,一般都需要一个种子seed作为基准。一般都是默认拿当前时间戳作为种子,进行随机算法;

    www.cnblogs.com/greatfish/p/5845924.html

    这篇文章可以做一个完整的解释;

    www.h5jun.com/post/array-shuffle.html

    segmentfault.com/a/1190000005875191

    这些都是一些常见的洗牌算法;


    随机数组决定定时器开始和结束;


    这个也是通过Math.floor(Math.random() * array.length)这个知识点随机而来;




    经过我俩的讨论:




    个人拙见,多多指教

    感谢阅读

    github-PPT链接

    ptteng.github.io/PPT/PPT/js-02-what-is-shuffle.html#/

    腾讯视频链接

    v.qq.com/x/page/l0514dtsels.html

    -----------------------------------------------------------------------------------------------------------------------------------

    人生苦短,想学Python。

    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    相关文章

      网友评论

        本文标题:【Js-002】洗牌算法具体指的是什么?

        本文链接:https://www.haomeiwen.com/subject/fmikixtx.html