• 欢迎访问大姚哥前端笔记
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧
  • 欢迎留言o(∩_∩)o 哈哈

Fisher–Yates shuffle算法(洗牌算法)

H5游戏 dayaoge 367次浏览

Fisher–Yates算法

该算法每次随机选取一个数,然后将该数与数组中最后(或最前)的元素相交换(如果随机选中的是最后/最前的元素,则相当于没有发生交换);然后缩小选取数组的范围,去掉最后的元素,即之前随机抽取出的数。重复上面的过程,直到剩余数组的大小为1,即只有一个元素时结束。
ES6写法举栗:

function shuffle(arr){
	const endIndex = arr.length -2;
	for(let i = 0; i <= endIndex; i++){
		const j = i + Math.floor(Math.random() * (arr.length - i));
		[arr[i], arr[j]] = [arr[j], arr[i]];
	}
	return arr;
}
const a=Array.from({ length : 9},(v,i)=>i);
console.log(a);
console.log(shuffle(a));

我们看一下运行结果
TIM截图20171117103952

数组已经随机了。

利用数组sort()方法

我们其实可以结合数组自带的sort()方法编写出更简洁的代码来达到目的。中间变量以及值交换什么的都省了,虽然后台实现肯定还是会进行值交换的,但我们不关心,一切交给sort()让它自己处理。但这种方法也只是简洁而以,效果是不如上面介绍的算法的,因为随着数组元素越多,其随机性会变差。

function shuffle(array) {
    return array.sort(function() {
        return Math.random() - 0.5
    });
}

小白公园 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明Fisher–Yates shuffle算法(洗牌算法)
喜欢 (2)