Collections.shuffle() 是 Java 中 java.util.Collections 类提供的一个非常实用的工具方法，用于随机打乱集合中的元素。它的功能非常简单：将列表中的元素顺序打乱。

方法签名：

public static void shuffle(List<?> list)

基本功能：

  • 随机打乱列表 list 中的元素。这个方法会修改原列表，打乱其元素顺序。
  • 使用的是 Random 对象来生成随机数。

源码分析

shuffle() 方法的实现位于 java.util.Collections 类中。它的源码如下：

public static void shuffle(List<?> list) {
    Random rnd = new Random();
    shuffle(list, rnd);
}
  • 方法说明：
    • shuffle(List<?> list)：接受一个 List 类型的参数，打乱列表中的元素顺序。
    • Random rnd = new Random();：默认使用 Random 类的实例生成随机数。
    • shuffle(list, rnd)：调用重载的 shuffle(List<?> list, Random rnd) 方法，传递生成的随机数对象。

重载方法：

public static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size(); i > 1; i--) {
        int j = rnd.nextInt(i);  // 生成 [0, i) 范围的随机数
        Collections.swap(list, i - 1, j);  // 交换元素
    }
}

详细分析：

  1. 生成随机数：
    • rnd.nextInt(i)：生成一个随机的整数 j，这个整数范围是 [0, i)，即小于 i 的整数。这里的 i 是 list.size() 的值，表示当前需要打乱的元素的数量。随着 i 的逐步递减，随机选择的范围也逐步缩小。
  2. 交换元素：
    • Collections.swap(list, i - 1, j)：swap() 方法用于交换列表中两个位置的元素。它接受三个参数：
      • list：需要操作的列表。
      • i - 1：当前元素的位置。
      • j：生成的随机位置，表示与当前位置 i - 1 交换。
  3. 迭代过程：
    • 循环从 list.size() 开始，逐步减少到 2（即 i > 1）。每次循环都会随机选择一个位置 j，然后将当前元素（i-1 位置）与 j 位置的元素交换。每次交换会使得当前元素在剩余未排序的元素中被随机分配，从而完成随机打乱的过程。

工作原理：

  • 从列表的最后一个元素开始，随机选择一个索引与当前元素交换。
  • 然后缩小待打乱的范围，即将最后一个元素视为已经排序，继续对剩余的元素进行打乱，直到剩下的元素只有一个。

算法分析：

  • Collections.shuffle() 使用的是 Fisher-Yates 洗牌算法（又叫 Knuth shuffle）。该算法的核心思想是通过不断随机交换，确保每个元素在最终列表中出现的位置是随机的。其时间复杂度是 O(n)，其中 n 是列表中元素的数量。

Fisher-Yates 算法的步骤：

  1. 从列表的最后一个元素开始，选择一个范围内的随机索引。
  2. 将当前元素与随机选择的元素交换。
  3. 逐步减少可交换范围，直到交换到列表的第二个元素。

这种方法保证了每个元素交换的概率相同，不会出现某些元素被“遗漏”或者“重复交换”的情况。

示例代码：

import java.util.*;

public class ShuffleExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            list.add(i);
        }

        System.out.println("Original list: " + list);
        
        // 打乱列表
        Collections.shuffle(list);
        
        System.out.println("Shuffled list: " + list);
    }
}

输出：

Original list: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Shuffled list: [3, 7, 2, 8, 6, 10, 1, 4, 9, 5]  // 每次输出都可能不同

总结：

  • Collections.shuffle() 是基于 Fisher-Yates 算法 的，具有 O(n) 的时间复杂度。
  • 它通过交换列表中的元素来实现随机打乱，确保了每个元素被选中的概率相同。
  • 默认使用 Random 类生成随机数，也可以通过重载方法传入一个自定义的 Random 实例。