我有一个这样的数组。
var arr1 = ["a", "b", "c", "d"];
我怎样才能随机化/洗牌呢?
事实上,无偏的洗牌算法是Fisher-Yates(又称Knuth)洗牌算法。
见https://github.com/coolaj86/knuth-shuffle
function shuffle(array) {
var currentIndex = array.length, temporaryValue, randomIndex;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// And swap it with the current element.
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
// Used like so
var arr = [2, 11, 37, 42];
arr = shuffle(arr);
console.log(arr);
一些更多的信息关于算法使用。
这里是Durstenfeld shuffle的JavaScript实现,这是Fisher-Yates的计算机优化版本。
/**
* Randomize array element order in-place.
* Using Durstenfeld shuffle algorithm.
*/
function shuffleArray(array) {
for (var i = array.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Fisher-Yates算法的工作原理是为每个原始数组元素挑选一个随机元素,然后将其从下一次抽签中排除。就像从一副牌中随机抽取一样。
这种排除法是以一种巧妙的方式完成的(由Durstenfeld发明,供计算机使用),将所选的元素与当前元素交换,然后从剩余的元素中挑选下一个随机元素。为了达到最佳的效率,这个循环是向后运行的,这样就简化了随机抽取的过程(它总是可以从0开始),并且跳过最后一个元素,因为已经没有其他选择了。
这个算法的运行时间是O(n)。请注意,洗牌是在原地进行的。所以如果你不想修改原始数组,可以先用.slice(0)
制作一个副本。
新的ES6允许我们一次赋值两个变量。当我们想交换两个变量的值时,这一点特别方便,因为我们可以在一行代码中完成。下面是同一函数的一个较短的形式,使用这一特性。
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
人们可以(或应该)把它作为Array的一个原形。
来自ChristopheD:
Array.prototype.shuffle = function() {
var i = this.length, j, temp;
if ( i == 0 ) return this;
while ( --i ) {
j = Math.floor( Math.random() * ( i + 1 ) );
temp = this[i];
this[i] = this[j];
this[j] = temp;
}
return this;
}