小课堂【郑州第六十七期】

一、背景介绍

洗牌算法是我们常见的随机问题，在玩游戏、随机排序时经常会碰到，本质是让一个数组内的元素随机排列。 

1999年，一个很流行的在线扑克平台的开发者开发的洗牌软件，带有很微小但很致命的漏洞，导致了灾难性的结果。 

黑客只要知道手中的两张牌和3张公用牌，就可以猜出转牌和河牌时会来什么牌，以及其他玩家的牌。

二、知识剖析

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法能够对一定规范的输入，在有限时间内获得所要求的输出。

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。

空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。

三、常见问题

洗牌算法的原理是什么？

四、解决方案

方法一：

从牌堆里随便抽一张出来，然后放在一边，之后从剩下的牌里重复之前的操作，直到所有牌都被抽出来放到了另一堆中。抽象到代码世界， 按相同的做法，就是随机从数组里取出一个元素，保存到另一个数组，然后重复之，直到原数组中所有元素都处理掉。

Demo:http://sandbox.runjs.cn/show/1hylhpck

代码：

function shuffle(array) {

    var copy = [],

      n = array.length,

      i;

    // 如果还剩有元素则继续。。。

    while (n) {

        // 随机抽取一个元素

        i = Math.floor(Math.random() * array.length);

        // 如果这个元素之前没有被选中过。。

        if (i in array) {

            copy.push(array[i]);

            delete array[i];

            n--;

        }

    }

    return copy;

}

我们创建了一个copy数组，然后遍历目标数组，将其元素复制到copy数组里，同时将该元素从目标数组中删除，这样下次遍历的时候就可以跳过这个序号。

方法二：

首先，该方法选中数组的最后一个元素：

接下来确定挑选随机元素的范围，从数组的第一个元素到上一步选中的元素都属于这一范围：

确定范围后，从中随机挑选一个数，这里选择的元素是4：

然后交换最后一个元素和随即选中元素的值：

上面的交换完成后，相当于我们完成了对数组最后一个元素的随机处理。接下来选中数组内倒数第二的元素：

之所以从后往前处理，是因为这样便于确定随机选择的范围。这次我们假定随机到的元素为2:

接着交换倒数第一个元素和 2 号元素的值，完成对倒数第二个元素随机排列的处理。然后是选中倒数第三个元素，重复之前的操作：

剩下的就是一些重复性的工作，不多做介绍了。

Demo:http://sandbox.runjs.cn/show/jabgttzr

代码：

  Array.prototype.shuffle = function() {

    var input = this;

    for (var i = input.length - 1; i >= 0; i--) {

      //获取小于this.length的随机整数

      var randomIndex = Math.floor(Math.random() * (i + 1));

      var itemAtIdex = input[randomIndex];

      input[randomIndex] = input[i];

      input[i] = itemAtIdex;

      //input[randomIndex]和input[i]交换值

    }

    return input;

  }

shuffle 函数挂载在 Array 对象的原型之下，便于数组直接调用该函数。在 shuffle 函数内部，this 引用的就是调用该 shuffle 的数组。 用一个新的变量引用 this，也就是调用 shuffle 函数的数组。接下来的for循环用于遍历所有数组内的所有元素，并进行随机交换。 注意，遍历顺序是从后往前进行的，也就是说从 input.length-1 位置的元素开始，知道遍历到数组中的第一个元素。遍历过程中的位置由变量 i 指定。 接下来，使用了两行代码在指定范围内挑选一个随机元素。 变量randomIndex存储了一个随机数，该随机数可以用作数组的索引，进而提取一个随机元素。注意，该随机数的最大值并不是数组的长度，而是变量i的值。 确定了随机元素的索引之后，用新的变量保存该元素的值，然后交换选中元素和随机元素的值。

五、编码实战

六、拓展思考

怎么保证这个算法得到的数组是完全随机的（即等概）？

原理：首先创建一个数组（如 [0, 1, 2 ... 18, 19, 20]），然后使用本文中的洗牌算法重新排序， 排序完成后记录每一个元素的值……以此步骤执行 10000 次，最后对同一索引位置上的数值进行求和。如此执行10000次后，索引之间的总值应该相差不大。

七、参考文献

参考一：洗牌算法：给数组随机排序

参考二： 由乱序播放说开了去

参考三： 当随机不够随机：一个在线扑克游戏的教训

参考四： 随机问题之--洗牌算法

八、更多讨论

还有没有更好用的洗牌算法

ppt链接：https://ptteng.github.io/PPT/PPT/JS-02-shuffle%20algorithm.html

视频链接：https://v.qq.com/x/page/f03891g1hcl.html