未加星标

42.洗牌算法(shuffle)的js实现

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二04 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏
洗牌算法(shuffle)的js实现 Fisher-Yates

先看最经典的 Fisher-Yates 的洗牌算法

这里有一个该算法的 可视化实现

其算法思想就是 从原始数组中随机抽取一个新的元素到新数组中

从还没处理的数组(假如还剩n个)中,产生一个[0, n]之间的随机数 random 从剩下的n个元素中把第 random 个元素取出到新数组中 删除原数组第random个元素 重复第 2 3 步直到所有元素取完 最终返回一个新的打乱的数组

按步骤一步一步来就很简单的实现

function shuffle(arr){ var result = [], random; while(arr.length>0){ random = Math.floor(Math.random() * arr.length); result.push(arr[random]) arr.splice(random, 1) } return result; }

这种算法要去除原数组 arr 中的元素,所以时间复杂度为 O(n2)

Knuth-Durstenfeld Shuffle

Fisher-Yates 洗牌算法的一个变种是 Knuth Shuffle

每次从未处理的数组中随机取一个元素,然后把该元素放到数组的尾部,即数组的尾部放的就是已经处理过的元素,这是一种原地打乱的算法,每个元素随机概率也相等,时间复杂度从 Fisher 算法的 O(n2)提升到了 O(n)

选取数组(长度n)中最后一个元素(arr[length-1]),将其与n个元素中的任意一个交换,此时最后一个元素已经确定 选取倒数第二个元素(arr[length-2]),将其与n-1个元素中的任意一个交换 重复第 1 2 步,直到剩下1个元素为止 function shuffle(arr){ var length = arr.length, temp, random; while(0 != length){ random = Math.floor(Math.random() * length) length--; // swap temp = arr[length]; arr[length] = arr[random]; arr[random] = temp; } return arr; }

Durstenfeld Shuffle的算法是从数组第一个开始,和Knuth的区别是遍历的方向不同

Other Array.sort()

利用Array的sort方法可以更简洁的实现打乱,对于数量小的数组来说足够。因为随着数组元素增加,随机性会变差。

[1,2,3,4,5,6].sort(function(){ return .5 - Math.random(); }) ES6

Knuth-Durstenfeld shuffle 的 ES6 实现,代码更简洁

function shuffle(arr){ let n = arr.length, random; while(0!=n){ random = (Math.random() * n--) >>> 0; // 无符号右移位运算符向下取整 [arr[n], arr[random]] = [arr[random], arr[n]] // ES6的结构赋值实现变量互换 } return arr; }

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

主题: 算法删除变量
分页:12
转载请注明
本文标题:42.洗牌算法(shuffle)的js实现
本站链接:http://www.codesec.net/view/481525.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(42)