下面是我之前一直使用的一个洗牌算法:
let arr = [1,2,3,4,5,6,7,8,9]; Array.prototype.shuffle = function() { let temp = this; for (let i = 0; i < temp.length; i++) { let index = Math.floor(Math.random()*temp.length); let itemAtIndex = temp[index]; temp[index] = temp[i] temp[i] = itemAtIndex; } return this; } console.log(arr.shuffle());
但仔细想想,其实这是非常不合理的,因为已经交换过的位置,下次仍然可能会被选上。
比较好的做法是排除已经交换过的位置,将剩下的位置洗牌,如下:
/*
1. 选中第一个元素,将其与n个元素中的任意一个交换(包括自己)。这时可以确定第一个元素
2. 选中第二个元素,将其与n-1个元素中的任意一个交换(包括自己)。确定第二个元素
3. 重复上面步骤,直到剩下一个。
4. 该算法事件复杂度为O(n),无偏差,各元素随机概率相等
*/
let arr = [1,2,3,4,5,6,7,8,9];
Array.prototype.shuffle = function() {
let temp = this;
for (let i = temp.length - 1; i >= 0; i--) {
let index = Math.floor(Math.random()*(i+1));
let itemAtIndex = temp[index];
temp[index] = temp[i]
temp[i] = itemAtIndex;
}
return this;
}
console.log(arr.shuffle());