JavaScript 数组随机化：Fisher-Yates 洗牌算法

在编程中，经常需要对数组进行随机化操作，也就是打乱数组元素的顺序。Fisher-Yates 洗牌算法（也称为 Knuth Shuffle）是实现这一目标的标准方法。本文将介绍这种算法，并展示如何在 JavaScript 中实现它。

Fisher-Yates 洗牌算法简介

Fisher-Yates 洗牌算法的核心思想是遍历数组，从最后一个元素开始，每次将当前元素与之前的任意一个元素交换，直到遍历完整个数组。这个过程确保每个元素都有相同的概率出现在每一个位置上，从而实现公平随机化。

JavaScript 实现

我们可以用不同的方式在 JavaScript 中实现 Fisher-Yates 洗牌算法。以下是两种常见的实现方式。

实现一：传统实现

以下是一个较为传统的实现方式：

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]];
  }
}

// 示例使用
let arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);

在这个实现中，Math.floor(Math.random() * currentIndex) 用于生成一个介于 0 和当前索引之间的随机数，然后交换当前元素与该随机索引对应的元素。

实现二：Durstenfeld 算法（优化版）

Durstenfeld 洗牌算法是 Fisher-Yates 算法的优化版本。它从数组末尾开始，每次随机选择一个元素，并与当前元素交换。这种方法避免了在数组开始部分的多余操作，从而提高了效率。

以下是用 ES6 实现的 Durstenfeld 算法：

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]];
    }
}

// 示例使用
let arr = ["a", "b", "c", "d"];
shuffleArray(arr);
console.log(arr);

在这个实现中，我们使用了 ES6 的数组解构赋值语法，使交换操作更为简洁。

关键点总结

公平性：Fisher-Yates 洗牌算法确保每个元素都有相同的概率出现在每一个位置上。
时间复杂度：该算法的时间复杂度为 O(n)，其中 n 是数组的长度。
空间复杂度：该算法在原地进行，空间复杂度为 O(1)，不需要额外的存储空间。

注意事项

输入验证：在实际应用中，最好先验证输入是否为数组，以防止因输入类型错误导致程序崩溃。
随机数生成器的质量：Math.random() 是伪随机数生成器，虽然足够大多数用途，但对高安全性需求的应用，可能需要使用更复杂的随机数生成器。