大家好，又见面了，我是你们的朋友全栈君。
洗牌算法
1. 背景
阿里的面试的时候做的一道笔试题:题目：写一个方法,入参为自然数n (n > 0)，返回一个自然数数组，数组长度为n，元素为[1,n]之间，且每个元素不重复，数组中各元素顺序要求随机；
实例1： 输入: N = 3 输出: 132
实例2： 输入: N = 5 输出: 32514
当时我的解法(写了两种方法)：
写的好烂，面完和面试官交流的时候面试官让我看下Collections.shuffle的源码，于是乎就开始研究这个“洗牌算法”。
2.洗牌算法
洗牌就是将原有的排序打乱的一个过程，我们可以通过抽牌、换牌和插牌三种方式进行洗牌。最常用的洗牌算法：即Fisher-Yates Shuffle和Knuth-Durstenfeld Shhuffle，我们分别学习一下两种洗牌算法。
2.1 Fisher-Yates Shuffle
所述费舍尔-耶茨洗牌是一种算法：用于产生随机排列的有限的序列，简单地说，该算法对序列进行洗牌。
算法的自然语言描述为(给定1到N的序列)：①记下从1到N的数字。
②从1到结尾的未删除数字(包括)之间选择一个随机数k。
③从低端开始计数，剔除尚未剔除的第k个数字，并将其写下一个单独的列表的末尾。
④从第2步开始重复，直到所有数字都被删除。
⑤现在在步骤3中写下的数字序列就是原始序列的随机排列。
理论上的费舍尔-耶茨洗牌算法的时间复杂度为O(n²)，空间复杂度O(n)。
2.2 Knuth-Durstenfeld Shuffle
所述克努斯-杜斯腾菲尔德算法是一个现代版的费舍尔-耶茨算法，我们实现Fisher和Yates算法时会花费不必要的时间来用来计算上面第3步中的剩余数字，但Durstenfeld的解决方案是将“删除”的数字移到列表的末尾，然后将每个被删除的数字交换为最后一个未删除的数字迭代，简言之：每次迭代时交换这个被取出的数字到原始列表的最后。这将算法的时间复杂度从O(n²)降低到了O(n)。
伪代码实现：//To shuffle an arrayaofnelements (indices 0…n-1):
forifromn−1down to1do
j← random integer such that 0 ≤j≤iexchangea[j] anda[i]
按照上述的伪代码的描述，我们使用JS实现这段伪代码：
使用ES6实现的
Knuth-Durstenfeld Shuffle
算法需要的时间正比于要随机置乱的数，不需要额为的存储空间开销，时间复杂度为O(n)，空间复杂度O(1)。
3.
Collections.shuffle()
源码解析：
shuffle方法的入口
传入待洗牌的List集合，定义一个随机数种子。
shuffle的具体实现
获取集合的长度，其中SHUFFLE_THRESHOLD = 5，当list的长度<5或者list实现了RandomAccess接口的时候，通过倒序的循环交换索引位置与随机生成的[0,i)的索引位置。
当集合长度>5的时候，将集合转为数组，然后再次进行随机值交换，然后将数组重新set到集合里面去，这样做避免了将“顺序访问”列表洗牌到适当的位置而导致的二次行为。
主意事项：
1)用List list=ArrayList(Arrays.asList(ia))，用shuffle()打乱不会改变底层数组的顺序。
2)用List list=Arrays.aslist(ia)，然后用shuffle()打乱会改变底层数组的顺序。
可以使用洗牌算法实现扫雷。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/126128.html原文链接：https://javaforall.net
