Fisher-Yates算法实现详解

来到golang学习网的大家，相信都是编程学习爱好者，希望在这里学习文章相关编程知识。下面本篇文章就来带大家聊聊《Fisher-Yates洗牌算法实现方法》，介绍一下，希望对大家的知识积累有所帮助，助力实战开发！

Fisher-Yates洗牌算法可高效公平地乱序数组，从末尾遍历，每次与前面随机位置交换，确保每种排列概率相等，时间复杂度O(n)，空间复杂度O(1)，JavaScript实现推荐使用原地交换，避免使用sort()结合Math.random()造成分布偏差。

数组乱序是开发中常见的需求，比如实现随机轮播、抽奖或游戏发牌。Fisher-Yates 洗牌算法是一种高效且公平的打乱数组顺序的方法，能确保每个排列出现的概率相等。

算法原理

Fisher-Yates 洗牌算法的核心思想是从数组末尾开始，依次与前面（包括自身）的一个随机位置交换元素。这样每一步都保证未处理的部分是等概率参与随机化的。

现代版本通常采用原地修改的方式，时间复杂度为 O(n)，空间复杂度为 O(1)。

JavaScript 实现

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

说明：

• 从最后一个元素开始遍历到第二个（索引 1）
• 每次生成一个从 0 到 i 的随机索引 j
• 交换位置 i 和 j 上的元素
• 返回原数组（已被修改）

使用示例

你可以这样使用这个函数：

const numbers = [1, 2, 3, 4, 5];
console.log(shuffleArray([...numbers])); // 每次运行结果不同

注意：如果不想修改原数组，调用时使用展开运算符 [...array] 创建副本。

常见误区

有些人会使用 sort() + Math.random() 来打乱数组：

不推荐写法：

// ❌ 不公平，可能导致偏差
numbers.sort(() => Math.random() - 0.5);

这种做法看似简单，但浏览器的排序算法并非为随机比较设计，会导致某些排列更可能出现，破坏随机性。

基本上就这些。Fisher-Yates 是目前最可靠的选择，理解原理后实现也很简单。实际项目中建议封装成工具函数复用。

今天关于《Fisher-Yates算法实现详解》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！