Fisher–Yates洗牌算法

1. 简介

Fisher-Yates 洗牌算法（也称为 Knuth 洗牌算法）是生成一个序列随机排列的高效、正确且简单的算法。它的核心目标是公平地打乱一个有限序列（如数组、列表），使得每一个可能的排列出现的概率都严格相等

2. 例子

例子1：将给定数组：[1, 2, 3, 4, 5, 6, 7, 8, 9]通过相同概率洗牌打乱顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Arrays;
import java.util.Random;

public class ForwardFisherYatesShuffle {

    public static void main(String[] args) {
        // 创建测试数组
        Integer[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println("原始数组: " + Arrays.toString(numbers));

        // 洗牌
        shuffle(numbers);
        System.out.println("洗牌后:   " + Arrays.toString(numbers));

    }

    /**
     * 从前往后遍历的 Fisher-Yates 洗牌算法
     * @param array 要洗牌的数组
     */
    public static <T> void shuffle(T[] array) {
        Random random = new Random();
        int n = array.length;

        // 从第一个元素遍历到倒数第二个元素
        for (int i = 0; i < n - 1; i++) {
            // 在 [i, n-1] 范围内生成随机索引
            int j = i + random.nextInt(n - i);

            // 交换元素
            swap(array, i, j);
        }
    }

    /**
     * 交换数组中两个元素的位置
     */
    private static <T> void swap(T[] array, int i, int j) {
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

例子2：将给定一个大数组（元素不重复），通过相同概率取随机N个，需要考虑效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<String> getRandomUniqueDocuments(List<String> strList, Integer num) {
    // 处理空列表
    if (CollectionUtils.isEmpty(strList)) {
        return new ArrayList<>();
    }

    // 创建列表副本避免修改原始列表
    List<String> copyList = new ArrayList<>(strList);
    int size = copyList.size();
    int n = Math.min(num, size);  // 确定实际需要选取的数量

    // 使用Fisher-Yates算法部分洗牌（仅打乱前n个元素）
    Random random = new Random();
    for (int i = 0; i < n; i++) {
        int j = i + random.nextInt(size - i);
        Collections.swap(copyList, i, j);
    }

    // 返回前n个元素（已随机化）
    return new ArrayList<>(copyList.subList(0, n));
}

3. 总结

Fisher-Yates (Knuth) 洗牌算法是一种高效、原地、并能严格保证生成均匀随机排列的标准算法，通过从后向前遍历数组并在每一步随机交换当前元素与一个它之前的（包含自身）随机位置的元素来实现完美洗牌。务必注意随机索引 j 的范围是 [i, n-i]

  • 核心目标：将一个数组（或列表）中的元素随机地重新排列，生成一个均匀随机排列——即每一个可能的排列出现的概率都完全相同
  • 核心思想：算法通过迭代和交换元素来实现洗牌。它从数组的开头开始，逐步向末尾移动
  • 高效： 只需要进行 n-1 次交换操作和 n-1 次随机数生成，时间复杂度为 O(n)，对于洗牌任务来说这是最优的