Knuth 洗牌算法

有时会遇到这样的题目：设计一个公平的洗牌算法。

与之类似的还有 随机打乱一个数组，其中用到的都是「随机算法」。

这类问题的核心在于“公平”、“随机”。

什么叫“公平”？

假设有一个长度为 $n$ 的数组（无重复元素），那么它的排列共有 $n!$ 种。

要做到公平，就要求等概率地返回这 $n!$ 种排列中地其中一种。

一种朴素的想法就是，生成所有 $n!$ 种排列，然后随机返回其中的一个。

毫无疑问这种算法是正确的，但是 $O(n!)$ 的时间复杂度是不可接受的，它是比指数爆炸 $2^n$ 还恐怖得多的存在。

换个角度思考，上面的要求等价于 每个元素等概率地出现在数组的每个位置。

就有了大名鼎鼎的 Knuth 洗牌算法，其实只有两行：

for (int i = nums.length - 1; i >= 0; i--) {
    swap(nums, i, random.nextInt(i + 1));
}

这两行代码就可以完成上述的目的。