如何随机打乱一个 JavaScript 数组？

技术背景

在 JavaScript 开发中，经常会遇到需要随机打乱数组元素顺序的需求，比如游戏中的洗牌、随机展示数据等。而实现这一需求的关键在于选择合适的随机打乱算法。

实现步骤

Fisher–Yates（aka Knuth）洗牌算法

这是一种被广泛认可的无偏洗牌算法。具体步骤如下：

从数组的最后一个元素开始，向前遍历。
对于每个位置 i，随机选择一个从 0 到 i 之间的索引 j。
交换位置 i 和 j 的元素。

代码示例

function shuffle(array) {
    let currentIndex = array.length;
    // 当还有元素需要打乱时
    while (currentIndex != 0) {
        // 选择一个剩余元素
        let randomIndex = Math.floor(Math.random() * currentIndex);
        currentIndex--;
        // 交换当前元素和随机选择的元素
        [array[currentIndex], array[randomIndex]] = [array[randomIndex], array[currentIndex]];
    }
    return array;
}

let arr = [2, 11, 37, 42];
let shuffledArr = shuffle(arr);
console.log(shuffledArr);

其他实现方式

使用 `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);

console.log(shuffled);

使用 `lodash` 库

import _ from 'lodash';
let numeric_array = [2, 4, 6, 9, 10];
let shuffled_num_array = _.shuffle(numeric_array);
console.log(shuffled_num_array);

最佳实践

对于大多数情况，推荐使用 Fisher–Yates 洗牌算法，因为它的时间复杂度为 $O(n)$，且能保证每个排列的概率相等。
如果需要对数组进行多次打乱操作，并且数组长度较大，建议使用 Fisher–Yates 算法的优化版本，避免不必要的元素交换。
如果对随机性要求不高，且数组长度较小，可以使用简单的 sort 方法结合 Math.random() 来实现，但要注意这种方法存在一定的偏差。

常见问题

使用 `sort` 方法打乱数组存在偏差

使用 array.sort(() => Math.random() - 0.5) 这种方式打乱数组时，由于 sort 方法的实现机制，可能会导致某些排列的概率更高，从而产生偏差。因此，不建议在对随机性要求较高的场景中使用这种方法。

避免修改原数组

如果不希望修改原数组，可以在打乱之前先复制一份数组，然后对复制后的数组进行操作。例如：

function shuffleWithoutModifyingOriginal(array) {
    let newArray = [...array];
    return shuffle(newArray);
}

let originalArr = [1, 2, 3];
let shuffledCopy = shuffleWithoutModifyingOriginal(originalArr);
console.log(originalArr); // 原数组不变
console.log(shuffledCopy); // 打乱后的数组

性能问题

在处理大规模数组时，一些算法可能会导致性能问题。例如，使用 splice 方法在循环中删除元素会使时间复杂度增加，建议使用更高效的算法，如 Fisher–Yates 算法。