简单易用的Knuth公平洗牌算法（给一个数组随机排序）

洗牌算法的重要原则就是“全面”而且“公平”，并且要使用尽可能小的时间复杂度来实现。

什么叫公平呢？一旦你开始思考这个问题，其实答案不难想到。洗牌的结果是所有元素的一个排列。一副牌如果有 n 个元素，最终排列的可能性一共有 n! 个。公平的洗牌算法，应该能等概率地给出这 n! 个结果中的任意一个。

如思考到这一点，我们就能设计出一个简单的暴力算法了：对于 n 个元素，生成所有的 n! 个排列，然后，随机抽一个。
这个算法绝对是公平的。但问题是，复杂度太高。复杂度是多少呢？**O(n!)**。因为，n 个元素一共有 n! 种排列，我们求出所有 n! 种排列，至少需要 n! 的时间。

那么这个问题的最优解肯定不是这样的， 我们只需要讲这个一般问题特殊化，只要保证特殊化的解法属于n！排列中的一种即可，Knuth算法就是这样做的。

算法的过程很简单，假设有**[1,2,3,4,5]**这样一个数组，每次随机过程，都在头部数组中随机选取一个数组，和候选区域的尾部数字进行交换，交换完毕后当前的候选区域尾部数字进入到固定区域，以此循环n次即可，以下面几张图来表示过程及概率：

可以看到每一个数字出现在当前位置的几率都是1/5，所以满足了公平性，虽然进行了特殊化处理，但最终的结果一定是符合条件的。非常巧妙，最后给出JS简要代码，其他语言的代码逻辑类似。

1
2
3
4
5
6
7
8

let arr = [1,2,3,4,5]

for (let i = arr.length - 1; i >= 0; i--) {
    let randomIndex = Math.floor(Math.random() * i) // 确定候选区域的随机索引
    let temp = arr[i] // 进行交换
    arr[i] = arr[randomIndex]
    arr[randomIndex] = temp
}

如有疑问，欢迎添加我的个人微信：