喜迎
春节

Fisher-Yates 洗牌算法

PHP 算法 Fisher-Yates
算法
发布日期:   2025-11-20
文章字数:   515
阅读时长:   2 分

Fisher-Yates 洗牌算法（也称为 Knuth 洗牌）是一种高效且公正的随机洗牌算法，用于将数组或列表中的元素随机重新排列。

🎯 算法原理

核心思想：从后往前遍历数组，将当前元素与随机位置的一个元素交换。

📝 算法步骤

原始版本：

1
2
3
4
// 从后往前遍历
for i from n-1 down to 1 do:
    j = 随机整数 (0 ≤ j ≤ i)
    交换 array[i] 和 array[j]

现代版本（Knuth 改进）：

1
2
3
4
// 从前往后遍历（更直观）
for i from 0 to n-2 do:
    j = 随机整数 (i ≤ j ≤ n-1)
    交换 array[i] 和 array[j]

🔢 示例演示

假设数组：[1, 2, 3, 4, 5]

步骤：

  1. i=0: j=随机(0-4)，假设 j=2 → 交换 arr[0] 和 arr[2]
    • 数组变为：[3, 2, 1, 4, 5]
  2. i=1: j=随机(1-4)，假设 j=3 → 交换 arr[1] 和 arr[3]
    • 数组变为：[3, 4, 1, 2, 5]
  3. i=2: j=随机(2-4)，假设 j=2 → 无交换
    • 数组保持：[3, 4, 1, 2, 5]
  4. i=3: j=随机(3-4)，假设 j=4 → 交换 arr[3] 和 arr[4]
    • 最终结果：[3, 4, 1, 5, 2]

💻 代码实现

PHP 实现：

1
2
3
4
5
6
7
8
9
10
11
12
function fisherYatesShuffle(array &$array): void
{
    $count = count($array);
    for ($i = $count - 1; $i > 0; $i--) {
        $j = random_int(0, $i);  // 生成 0 到 i 的随机整数
        [$array[$i], $array[$j]] = [$array[$j], $array[$i]];
    }
}

// 使用示例
$girds = [1, 2, 3, 4, 5];
fisherYatesShuffle($girds);

JavaScript 实现：

1
2
3
4
5
6
7
function fisherYatesShuffle(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. 均匀分布：每个排列出现的概率相等
  2. 时间复杂度：O(n) - 非常高效
  3. 空间复杂度：O(1) - 原地操作
  4. 无偏性：真正的随机洗牌

❌ 对比其他方法的劣势

错误方法示例：

1
2
3
4
5
6
7
8
// ❌ 错误：非均匀分布
array.sort(() => Math.random() - 0.5);

// ❌ 错误：可能重复交换，效率低
for (let i = 0; i < array.length; i++) {
    const j = Math.floor(Math.random() * array.length);
    [array[i], array[j]] = [array[j], array[i]];
}

Fisher-Yates 是洗牌算法的黄金标准，在需要真正随机排列时应该优先选择它。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/fisher-yates.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 Fisher-Yates
赏
评 论
 上一篇
状态同步与帧同步：多人游戏网络同步技术深度解析
状态同步与帧同步：多人游戏网络同步技术深度解析
如何让分布在世界各地的玩家在虚拟世界中实现流畅的多人互动？状态同步和帧同步提供了两种不同的技术路径，各自在游戏开发中扮演着重要角色。 问题背景在多人游戏开发中，网络同步是核心技术挑战： 网络延迟：玩家之间的网络延迟从几十毫秒到几百毫秒
2025-11-20 算法
算法 状态同步 帧同步
下一篇 
加权随机算法：按权重控制的概率选择机制
加权随机算法：按权重控制的概率选择机制
如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。 问题背景在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机： 游戏开发：稀有装备1%概率，普通装备50%概率 推荐系统：热
2025-11-20 算法
PHP 算法 加权随机算法
PHP 算法 Fisher-Yates
算法
发布日期:   2025-11-20
文章字数:   515
阅读时长:   2 分

Fisher-Yates 洗牌算法（也称为 Knuth 洗牌）是一种高效且公正的随机洗牌算法，用于将数组或列表中的元素随机重新排列。

🎯 算法原理

核心思想：从后往前遍历数组，将当前元素与随机位置的一个元素交换。

📝 算法步骤

原始版本：

1
2
3
4
// 从后往前遍历
for i from n-1 down to 1 do:
    j = 随机整数 (0 ≤ j ≤ i)
    交换 array[i] 和 array[j]

现代版本（Knuth 改进）：

1
2
3
4
// 从前往后遍历（更直观）
for i from 0 to n-2 do:
    j = 随机整数 (i ≤ j ≤ n-1)
    交换 array[i] 和 array[j]

🔢 示例演示

假设数组：[1, 2, 3, 4, 5]

步骤：

  1. i=0: j=随机(0-4)，假设 j=2 → 交换 arr[0] 和 arr[2]
    • 数组变为：[3, 2, 1, 4, 5]
  2. i=1: j=随机(1-4)，假设 j=3 → 交换 arr[1] 和 arr[3]
    • 数组变为：[3, 4, 1, 2, 5]
  3. i=2: j=随机(2-4)，假设 j=2 → 无交换
    • 数组保持：[3, 4, 1, 2, 5]
  4. i=3: j=随机(3-4)，假设 j=4 → 交换 arr[3] 和 arr[4]
    • 最终结果：[3, 4, 1, 5, 2]

💻 代码实现

PHP 实现：

1
2
3
4
5
6
7
8
9
10
11
12
function fisherYatesShuffle(array &$array): void
{
    $count = count($array);
    for ($i = $count - 1; $i > 0; $i--) {
        $j = random_int(0, $i);  // 生成 0 到 i 的随机整数
        [$array[$i], $array[$j]] = [$array[$j], $array[$i]];
    }
}

// 使用示例
$girds = [1, 2, 3, 4, 5];
fisherYatesShuffle($girds);

JavaScript 实现：

1
2
3
4
5
6
7
function fisherYatesShuffle(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. 均匀分布：每个排列出现的概率相等
  2. 时间复杂度：O(n) - 非常高效
  3. 空间复杂度：O(1) - 原地操作
  4. 无偏性：真正的随机洗牌

❌ 对比其他方法的劣势

错误方法示例：

1
2
3
4
5
6
7
8
// ❌ 错误：非均匀分布
array.sort(() => Math.random() - 0.5);

// ❌ 错误：可能重复交换，效率低
for (let i = 0; i < array.length; i++) {
    const j = Math.floor(Math.random() * array.length);
    [array[i], array[j]] = [array[j], array[i]];
}

Fisher-Yates 是洗牌算法的黄金标准，在需要真正随机排列时应该优先选择它。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/fisher-yates.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 Fisher-Yates
赏
评 论
 上一篇
状态同步与帧同步：多人游戏网络同步技术深度解析
状态同步与帧同步：多人游戏网络同步技术深度解析
如何让分布在世界各地的玩家在虚拟世界中实现流畅的多人互动？状态同步和帧同步提供了两种不同的技术路径，各自在游戏开发中扮演着重要角色。 问题背景在多人游戏开发中，网络同步是核心技术挑战： 网络延迟：玩家之间的网络延迟从几十毫秒到几百毫秒
2025-11-20 算法
算法 状态同步 帧同步
下一篇 
加权随机算法：按权重控制的概率选择机制
加权随机算法：按权重控制的概率选择机制
如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。 问题背景在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机： 游戏开发：稀有装备1%概率，普通装备50%概率 推荐系统：热
2025-11-20 算法
PHP 算法 加权随机算法
PHP 算法 Fisher-Yates
算法
发布日期:   2025-11-20
文章字数:   515
阅读时长:   2 分

Fisher-Yates 洗牌算法（也称为 Knuth 洗牌）是一种高效且公正的随机洗牌算法，用于将数组或列表中的元素随机重新排列。

🎯 算法原理

核心思想：从后往前遍历数组，将当前元素与随机位置的一个元素交换。

📝 算法步骤

原始版本：

1
2
3
4
// 从后往前遍历
for i from n-1 down to 1 do:
    j = 随机整数 (0 ≤ j ≤ i)
    交换 array[i] 和 array[j]

现代版本（Knuth 改进）：

1
2
3
4
// 从前往后遍历（更直观）
for i from 0 to n-2 do:
    j = 随机整数 (i ≤ j ≤ n-1)
    交换 array[i] 和 array[j]

🔢 示例演示

假设数组：[1, 2, 3, 4, 5]

步骤：

  1. i=0: j=随机(0-4)，假设 j=2 → 交换 arr[0] 和 arr[2]
    • 数组变为：[3, 2, 1, 4, 5]
  2. i=1: j=随机(1-4)，假设 j=3 → 交换 arr[1] 和 arr[3]
    • 数组变为：[3, 4, 1, 2, 5]
  3. i=2: j=随机(2-4)，假设 j=2 → 无交换
    • 数组保持：[3, 4, 1, 2, 5]
  4. i=3: j=随机(3-4)，假设 j=4 → 交换 arr[3] 和 arr[4]
    • 最终结果：[3, 4, 1, 5, 2]

💻 代码实现

PHP 实现：

1
2
3
4
5
6
7
8
9
10
11
12
function fisherYatesShuffle(array &$array): void
{
    $count = count($array);
    for ($i = $count - 1; $i > 0; $i--) {
        $j = random_int(0, $i);  // 生成 0 到 i 的随机整数
        [$array[$i], $array[$j]] = [$array[$j], $array[$i]];
    }
}

// 使用示例
$girds = [1, 2, 3, 4, 5];
fisherYatesShuffle($girds);

JavaScript 实现：

1
2
3
4
5
6
7
function fisherYatesShuffle(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. 均匀分布：每个排列出现的概率相等
  2. 时间复杂度：O(n) - 非常高效
  3. 空间复杂度：O(1) - 原地操作
  4. 无偏性：真正的随机洗牌

❌ 对比其他方法的劣势

错误方法示例：

1
2
3
4
5
6
7
8
// ❌ 错误：非均匀分布
array.sort(() => Math.random() - 0.5);

// ❌ 错误：可能重复交换，效率低
for (let i = 0; i < array.length; i++) {
    const j = Math.floor(Math.random() * array.length);
    [array[i], array[j]] = [array[j], array[i]];
}

Fisher-Yates 是洗牌算法的黄金标准，在需要真正随机排列时应该优先选择它。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/fisher-yates.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 Fisher-Yates
赏
评 论
 上一篇
状态同步与帧同步：多人游戏网络同步技术深度解析
状态同步与帧同步：多人游戏网络同步技术深度解析
如何让分布在世界各地的玩家在虚拟世界中实现流畅的多人互动？状态同步和帧同步提供了两种不同的技术路径，各自在游戏开发中扮演着重要角色。 问题背景在多人游戏开发中，网络同步是核心技术挑战： 网络延迟：玩家之间的网络延迟从几十毫秒到几百毫秒
2025-11-20 算法
算法 状态同步 帧同步
下一篇 
加权随机算法：按权重控制的概率选择机制
加权随机算法：按权重控制的概率选择机制
如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。 问题背景在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机： 游戏开发：稀有装备1%概率，普通装备50%概率 推荐系统：热
2025-11-20 算法
PHP 算法 加权随机算法
  目录
  目录
  目录
hexo