洗牌算法

所谓的洗牌算法的应用，让我们来看看应用最多的场景。在我们的实际的开发中，我们经常会遇到一个需求，从数组中随机挑选出一个元素，这个时候，我们可以随机出一个数值作为数组元素的索引，即将一个随机值作为下标。但是，如果我们需要从数组随机中挑选出2个，3个甚至是n个元素怎么办？并且要求挑选出的元素不能重复。这个时候，如果我们还使用上边的方法，我们就需要在随机的时候确保现在的随机数和之前的每个随机数都不一样。这个时候，我们需要另一个数组来保存已经随机过的数组，随机数已经存在的时候，我们就需要重新随机。在这种情况下，如果需要挑选的数量少的情况下还好，如果需要挑选的数量比较多，那么后期的随机数已经出现的概论是很大的，我们就需要不断的去重复的去随机。这将在很大的程度上让程序提高执行时间，降低效率。

其实，我们需要换一下思路，当我们需要从一个数组中随机取值的时候，我们可以将数组先打乱，然后从中取前n个元素就好了。这样的是不是更好理解呢？但问题又来了。怎样才算是将数组打乱了呢？打乱又如何定义呢？对于打乱，我们可以分为2种情况来理解。

1. 所有的元素在同一个位置出现的可能性一致。
2. 同一元素在所有的位置出行的可能性一致。

对于实现打乱，我们首先能想到的就是对数组元素进行全排列，然后我们随机从中选择一种排列，再从中取前n个值，就可以实现我们的需求。但问题是，全排列的个数是n!。所以我们的时间复杂度也就是O(n!)。这个时间复杂度，我们在实际的工作中，一般是无法接受的。那么我们是不是可以换一种思路来实现打乱呢？答案是肯定的。这就是唐纳德为我们提供的关于洗牌算法的解决方案。代码简单，易懂。

首先，让我们先看看代码是如何实现的：

function randomArray(array) {
  const result = array.slice();
  const len = result.length - 1;
  for (let i = len; i > 1; i--) {
    const random = Math.floor(Math.random() * i);
    [result[i], result[random]] = [result[random], result[i]];
  }
  return result;
}

从代码中，我们可以看出，这个算法的时间复杂度为O(n)。那么就让我们仔细看看这个算法都做了一些什么，又为什么可以保证”打乱“。首先，我们解读一下代码做的事情：

1. 首先，我们随机一个数值，这个数值在一定的范围内，而且范围原来越小。从代码中，我们认真研究一下，就知道这个随机数的范围，每次都比上一次小1.
2. 然后，我们将随机的下标对应的数值和后边的一个数值进行交互。

单单从代码来看，可能比较难以理解。那么我们来说说我们的思路，这段代码就容易理解。

既然我们需要保证同一个元素在所有位置出现的可能性一致。那么，我们就可以从某个元素开始，将其放到任意一个位置，然后再对下一个元素执行同样的操作。为了编码方便，我们选择从最后一个元素开始，依次向前。

1. 将最后一个元素随机和某个元素交互位置，包括它自己，那么，我们就保证了这个位置出现每个元素的概论都相等。
2. 除去最后一个元素，选择倒数第二个元素，将它和它之前的元素随机交换位置。那么它每个元素现在这个位置上的概论就是相等的。这里有个疑问，为什么不和最后一个元素交换位置。
3. 以此类推。

比如，我们需要随机打乱5个元素的数组。那么具体的执行操作就是这样的。假如排序的数组为：[1,2,3,4,5]。

1. 对于最后一个位置，出现任意一个数的可能性都一样，都是1/5。
2. 假设第一次的随机数为2。则交换后的数组为[1,2,5,4,3]。这个时候，需要看倒数第二个位置出现每个数的概论都是多少：
   1. 对于每个元素，没有被交换的概论为4/5，然后此次出现在此位置的概论为1/4。其总概论为4/5*1/4=1/5。
3. 假设上次的随机数为1。则交换后的数组为[1,4,5,2,3]。这个时候，我们需要看倒数第三个位置出现每个数的概论是多少：
   1. 对于每个元素，前两次没有被交换的概论为4/5*3/4=3/5。然后此次出现在此位置上的概论为1/3。总概论为3/5*/3=1/5。
4. 对于接下来的验证是一致的。

这就是我们的洗牌算法，简单而使用。