Java数组实现费雪-耶茨算法教程

本文深入讲解了如何在Java中用数组手动实现费雪-耶茨（Fisher-Yates）随机乱序算法——一种时间复杂度为O(n)、原地操作且严格保证每种排列出现概率完全相等的经典洗牌算法；通过从后往前遍历、精准使用Random.nextInt(i+1)生成[0,i]内随机索引并交换，避开正向遍历、边界错误、重复创建Random等常见陷阱，同时延伸至泛型支持与线程安全优化（如ThreadLocalRandom），助你不仅“会用”，更真正理解Collections.shuffle()背后的原理与设计智慧。

在 Java 中用数组实现费雪-耶茨（Fisher-Yates）随机乱序算法，核心是“从后往前遍历，每次随机选一个位置与当前位交换”。它时间复杂度 O(n)，原地打乱，且每种排列概率均等，比 Collections.shuffle() 自己动手更利于理解原理。

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

费雪-耶茨标准洗牌（现代版本）的关键思想是： 对长度为 n 的数组，从索引 n−1 开始，到索引 1（即第二个元素），依次执行： → 随机选择一个索引 j，满足 0 ≤ j ≤ i； → 将 arr[i] 与 arr[j] 交换。 这样，每一轮都把一个“尚未确定位置”的元素随机放到当前末尾位置，保证后续不再动它。

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

以下是基于 int[] 的通用实现，使用 java.util.Random：

import java.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;
}
}

说明：

• 边界注意：循环从 i = arr.length - 1 到 i = 1（包含），不需处理 i=0，因为只剩一个元素时已自然“固定”
• nextInt(i + 1) 是关键：确保 j ∈ [0, i]，不是 [0, i)，否则会漏掉当前位置自身，破坏均匀性
• 支持任意类型数组：把 int[] 替换为 T[] 并加泛型即可（需注意泛型数组创建限制）

常见错误与避坑提示

初学者易犯的几个典型问题：

• 正向遍历（i 从 0 到 n−2）：若写成 for (int i = 0; i 并随机选 j ∈ [i, n−1]，虽能打乱但概率不均等——某些排列出现概率偏高
• 随机范围写错：如用 rand.nextInt(i)（范围 [0,i)），会导致 arr[i] 永远无法和自己交换，丢失一种可能状态
• 重复创建 Random 实例：在频繁调用的 shuffle 方法里每次都 new Random()，可能因系统时间种子相近导致短时间多次调用结果雷同；建议复用同一 Random 实例或用 ThreadLocalRandom.current()

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

如需在多线程环境安全使用，推荐：

• 用 ThreadLocalRandom.current().nextInt(i + 1) 替代 new Random()
• 泛型版本可定义为：public static void shuffle(T[] arr)，交换逻辑不变，只需注意 T 不可为基本类型（需用包装类如 Integer[]）
• 若必须处理基本类型数组（如 int[]、double[]），仍需单独写对应重载方法

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~