公平的洗牌算法 | Knuth-Shuffle

发表于 更新于 分类于

给定一个集合，我们有很多办法能够对这个集合快速排序，但如果给一个已经排序过的集合，如何公平随机地打乱它呢？

问题特点

此类问题最大的特点就是要公平公平还是TMD公平！。何为公平，洗牌的结果是所有元素排成一列，如果一副牌有 n 个元素，最终排列的结果就有 n! 个，公平的洗牌算法要保证能等概率地给出这 n! 个结果中的任意一个。

应用场景

  1. 可以用来洗牌哈；
  2. 随机不重复地播放列表中的歌曲；
  3. 扫雷，雷的初始化；
  4. client 将 所有 servers 的 ip 随机打乱，做负载均衡。

其他解决方案

在介绍洗牌算法前，先介绍一些其他简单而又暴力的解决方式，一起来品一品：
一：穷举 n! 个结果，随机选择一个，算法是绝对公平了，但是时间复杂度达到了 O(N!)，直接螺旋升天。
image.png

二：用 random() % n 的方式，不停地随机选取一个数，放入另外一个数组中，直至原数组中的每个数都被选中过。这样的问题是可能会随机到重复的数，你可能需要维护一个 Set 来确保每个数只被选取一次，且越到后来，随机到重复数字的概率越高，算法性能也非常差。

洗牌算法

无比简单，只要一句话就能概括：从最后一个元素开始，随机地和前面所有元素中的某一个进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void randomizedArray(Object[] array) {
    int p = array.length;
    while (p > 0) {
        int index  = (int) Math.floor(Math.random() * p--);
        swap(array, index, p);
    }
}

public static void swap(Object[] values, int i, int j) {
    Object tmp = values[i];
    values[i] = values[j];
    values[j] = tmp;
}

KnuthShuffle.java