Fisher Yates模型在JavaScript中的工作原理及循环逻辑疑问

Fisher-Yates 是一种高效的无偏洗牌算法，核心是从数组末尾向前遍历，每次将当前位置的元素与前面随机选中的一个未洗牌元素交换，避免重复操作和概率偏倚。

循环逻辑拆解 #

针对你困惑的循环部分，一步步拆解核心逻辑：

• 循环从数组最后一个元素（索引array.length - 1）开始，向前遍历到第二个元素（索引1），无需处理第一个元素（索引0）——当遍历到它时，前面已经没有未洗牌的元素了。
• 每一步生成的随机索引范围是[0, 当前索引]：这个范围确保我们只从还没被洗牌的前半段元素里选择，不会触碰已经固定在末尾的已洗牌元素。
• 交换当前索引元素和随机选中的元素：把选中的未洗牌元素放到当前的“已洗牌位置”，当前元素则进入未洗牌区域等待后续处理。

JavaScript 实现代码 #

function fisherYatesShuffle(array) {
  // 复制原数组，避免修改原数据
  const shuffled = [...array];
  // 从最后一个元素开始向前遍历
  for (let i = shuffled.length - 1; i > 0; i--) {
    // 生成0到i（包含i）的随机整数
    const randomIndex = Math.floor(Math.random() * (i + 1));
    // 交换当前元素和随机选中的元素
    [shuffled[i], shuffled[randomIndex]] = [shuffled[randomIndex], shuffled[i]];
  }
  return shuffled;
}

// 示例使用
const originalArray = [1, 2, 3, 4, 5];
const shuffledArray = fisherYatesShuffle(originalArray);
console.log(shuffledArray);

算法过程示意图 #

这张图直观展示了每一步循环中随机选择、交换元素的完整流程，能帮你快速对应代码逻辑和实际操作。

内容的提问来源于stack exchange，提问作者Reddy Nagendra