如何在 Java 中利用数组实现简单的费雪-耶茨（Fisher-Yates）随机乱序算法

如何在 Ja va 中利用数组实现简单的费雪-耶茨（Fisher-Yates）随机乱序算法

想在Ja va里给数组洗牌？自己动手实现费雪-耶茨算法是个绝佳的选择。它的核心逻辑非常清晰：从后往前遍历，每次随机选一个位置与当前位置交换。整个算法的时间复杂度是O(n)，直接在原数组上操作，更重要的是，它能保证每一种可能的排列出现的概率都完全相同。比起直接调用Collections.shuffle()，亲手实现一遍能让你对“真正均匀的随机”有更深刻的理解。

理解算法逻辑：从末尾开始逐个“固定”

现代版本的费雪-耶茨洗牌算法，其精妙之处在于一种逆向的“确定”思维。对于一个长度为 n 的数组，操作从索引 n−1（也就是最后一个元素）开始，一直进行到索引 1（第二个元素）。在每一轮中，只做两件事：
→ 随机选取一个索引 j，范围在 0 ≤ j ≤ i 之间；
→ 交换数组中 arr[i] 和 arr[j] 的值。
这个过程可以理解为：每一轮，你都把当前“待处理”的末尾位置（i），用一个从前面尚未“固定”的区域（0到i）中随机选出的元素来填充。一旦交换完成，这个位置 i 的元素在后续的步骤中就再也不动了，从而确保了随机过程的完备性和均匀性。

Ja va 数组实现步骤（含完整代码）

下面是一个基于 int[] 的基础实现，使用了标准的 ja va.util.Random 类：

import ja va.util.Random;
public static void shuffle(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    Random rand = new Random();
    for (int i = arr.length - 1; i > 0; i--) {
        int j = rand.nextInt(i + 1); // 生成 [0, i] 范围内的随机整数
        // 交换 arr[i] 和 arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

来看几个关键点：

立即学习“Ja va免费学习笔记（深入）”；

• 边界是关键：循环从 i = arr.length - 1 开始，到 i > 0 结束。这意味着当 i 等于 1 时执行最后一轮交换，i=0 的元素无需处理，因为它自然成为了唯一剩下的“固定”元素。
• nextInt(i + 1)是灵魂：这里必须用 i + 1 作为参数，以确保随机数 j 的取值范围包含当前位置 i 本身。如果错误地写成了 nextInt(i)，就会丢失“元素与自己交换”这种可能性，从而破坏整个排列空间的均匀性。
• 通用性扩展：这个逻辑可以轻松迁移到任何对象数组。只需将方法签名改为 public static void shuffle(T[] arr)，交换逻辑保持不变即可。当然，对于基本类型数组（如int、double），Ja va的泛型机制不支持，需要单独编写重载方法。

常见错误与避坑提示

即便是简单的算法，魔鬼也藏在细节里。以下是几个初学者最容易踩的坑：

• 错误的正向遍历：有人会想，从前往后遍历不行吗？比如写成 for (int i = 0; i < arr.length-1; i++) 并随机选择 j ∈ [i, n−1]。逻辑上确实能打乱数组，但数学上可以证明，这样产生的某些排列出现的概率会偏高，无法达到费雪-耶茨算法所保证的绝对均匀。
• 随机范围写错：正如前面强调的，rand.nextInt(i) 和 rand.nextInt(i+1) 有本质区别。前者会导致 arr[i] 永远没有机会留在原位，这相当于人为减少了一种可能的排列状态，是算法实现中的硬伤。
• 低效的Random实例创建：如果在频繁调用的shuffle方法内部每次都执行 new Random()，可能会因为系统时钟作为种子在极短时间内相近，导致连续多次调用产生高度相似的“随机”序列。正确的做法是复用同一个Random实例，或者在并发环境下使用 ThreadLocalRandom.current()。

进阶：线程安全与泛型支持

当你的应用场景变得复杂时，可以考虑以下进阶优化：

• 线程安全：在多线程环境下，最推荐的写法是使用 ThreadLocalRandom.current().nextInt(i + 1)。它为每个线程维护独立的随机数生成器，既安全又高效。
• 泛型版本：可以定义一个通用的方法：public static void shuffle(T[] arr)。内部交换逻辑完全一致。需要注意的是，泛型T不能是基本类型（如int, char）。
• 基本类型数组：如果需要处理大量的基本类型数组（如int[], double[]），由于Ja va的类型限制，目前仍需为每种基本类型编写单独的重载方法，这是性能与泛型便利性之间的一种权衡。