JavaScript中提供了sort()和reverse()方法对数组项重新排序。但很多时候这两个方法无法满足我们实际业务的需求，比如说扑克牌游戏中的随机洗牌，例如：
我有一个这样的数组，我怎样才能随机化/洗牌呢？
var arr = [2, 11, 37, 42];Fisher-Yates（又名 Knuth）洗牌
function shuffle(array) {
let currentIndex = array.length, randomIndex;
while (currentIndex != 0) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
[array[currentIndex], array[randomIndex]] = [
array[randomIndex], array[currentIndex]];
}
return array;
}
var arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);Fisher-Yates优化版本
这是Durstenfeld shuffle的 JavaScript 实现，这是 Fisher-Yates 的优化版本：
/* Randomize array 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;
}
}
它为每个原始数组元素选择一个随机元素，并将其从下一次抽奖中排除，就像从一副纸牌中随机选择一样。
这种巧妙的排除将选取的元素与当前元素交换，然后从余数中选取下一个随机元素，向后循环以获得最佳效率，确保随机选取得到简化（它始终可以从 0 开始），从而跳过最后一个元素。
算法运行时是O(n). 请注意，shuffle 是就地完成的，因此如果您不想修改原始数组，请先使用.slice(0).
ES6 / ECMAScript 2015
新的 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]];
}
}使用 map 和 sort
let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]
let shuffled = unshuffled
.map((value) => ({ value, sort: Math.random() }))
.sort((a, b) => a.sort - b.sort)
.map(({ value }) => value)
- 我们将数组中的每个元素放在一个对象中，并赋予它一个随机排序键
- 我们使用随机键排序
- 我们取消映射以获取原始对象
您可以对多态数组进行 shuffle，并且排序与 Math.random 一样随机，这对于大多数用途来说已经足够了。
由于元素根据每次迭代都不会重新生成的一致键进行排序，并且每次比较都从相同的分布中提取，因此 Math.random 分布中的任何非随机性都被抵消了。
速度
时间复杂度为 O(N log N)，与快速排序相同。空间复杂度为 O(N)。这不如 Fischer Yates shuffle 有效，但在我看来，代码明显更短且功能更强大。如果你有一个大数组，你当然应该使用 Fischer Yates。如果你有一个包含几百个项目的小数组，你可以这样做。
其他解决方案
其他解决方案只是为了好玩。
ES6 纯递归
const getShuffledArr = arr => {
if (arr.length === 1) {return arr};
const rand = Math.floor(Math.random() * arr.length);
return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))];
};
ES6 Pure 使用 array.map
function getShuffledArr (arr){
return [...arr].map( (_, i, arrCopy) => {
var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) );
[arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]]
return arrCopy[i]
})
}
ES6 Pure 使用 array.reduce
function getShuffledArr (arr){
return arr.reduce(
(newArr, _, i) => {
var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) );
[newArr[rand], newArr[i]] = [newArr[i], newArr[rand]]
return newArr
}, [...arr]
)
}本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！