大家好,又见面了,我是你们的朋友全栈君。
要求:给定一个长度为n的有序数组,要求将其完全打乱,每个元素在任何位置出现的概率均为1/n。
随机洗牌算法有好几个,这里讲其中的一个,Fisher-Yates shuffle算法(时间复杂度为O(n)),其思路如下:
(1)从数组中随机选取一个数p。
(2)将p与数组中最后(也可以是最前)的元素交换。(如果随机选中的是最后的元素,则相当于没有发生交换)
(3)去掉最后的元素(这里并没有删除操作,而是缩小索引值范围),即选中的p,缩小选取的数组范围。
(4)重复步骤(1)~(3),直到数组的长度为1时结束。
代码如下:
function shuffle(arr){
var tmp;
var len=arr.length;
if(len<=1){return arr;}
for(var i=len-1;i>0;i--){
var ind=Math.round(Math.random()*i); //随即产生0到i之间的一个数并将其四舍五入成一个整数,作为随机选中的元素的下标
tmp=arr[i];
arr[i]=arr[ind];
arr[ind]=tmp; //随机数与最后一个元素进行交换
}
return arr;
}
测试:
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/191012.html原文链接:https://javaforall.cn