function shuffle(array) {
let currentIndex = array.length, randomIndex;
// While there remain elements to shuffle.
while (currentIndex != 0) {
// Pick a remaining element.
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
// And swap it with the current element.
[array[currentIndex], array[randomIndex]] = [
array[randomIndex], array[currentIndex]];
}
return array;
}
// Used like so
var arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);
这是一个JavaScript实现的Durstenfeld shuffle,它是Fisher-Yates算法的优化版本:
它为每个原始数组元素选择一个随机元素,并从下一次抽取中排除它,就像从一副牌中随机抽取一样。
这个巧妙的排除操作将被选中的元素与当前元素交换,然后从剩余的元素中选择下一个随机元素,为了最佳效率而向后循环,确保随机选择被简化(它总是可以从0开始),从而跳过最后一个元素。
算法的运行时间为
O(n)
。请注意,洗牌是原地进行的,所以如果你不想修改原始数组,请先使用.slice(0)
创建一个副本。编辑:更新到ES6 / ECMAScript 2015
新的ES6允许我们同时赋值两个变量。当我们想要交换两个变量的值时,这特别方便,因为我们可以在一行代码中完成。这是使用此功能的同一函数的更短形式。
事实上,无偏的洗牌算法是Fisher-Yates(又称为Knuth)洗牌算法。
你可以在这里看到一个很棒的可视化效果(原始帖子链接到这里)