关于洗牌算法的错误认识

2018-06-24 02:02:09来源：未知阅读 ()

下面是我之前一直使用的一个洗牌算法：

    let arr = [1,2,3,4,5,6,7,8,9];

    Array.prototype.shuffle = function() {
      let temp = this;
      for (let i = 0; i < temp.length; i++) {
        let index       = Math.floor(Math.random()*temp.length);
        let itemAtIndex = temp[index];
        temp[index]     = temp[i]
        temp[i]         = itemAtIndex;
      }  
      return this;
    }
    console.log(arr.shuffle());

但仔细想想，其实这是非常不合理的，因为已经交换过的位置，下次仍然可能会被选上。

比较好的做法是排除已经交换过的位置，将剩下的位置洗牌，如下：

    /*
      1. 选中第一个元素，将其与n个元素中的任意一个交换（包括自己）。这时可以确定第一个元素
      2. 选中第二个元素，将其与n-1个元素中的任意一个交换（包括自己）。确定第二个元素
      3. 重复上面步骤，直到剩下一个。
      4. 该算法事件复杂度为O(n)，无偏差，各元素随机概率相等
    */
    let arr = [1,2,3,4,5,6,7,8,9];

    Array.prototype.shuffle = function() {
      let temp = this;
      for (let i = temp.length - 1; i >= 0; i--) {
        let index       = Math.floor(Math.random()*(i+1));
        let itemAtIndex = temp[index];
        temp[index]     = temp[i]
        temp[i]         = itemAtIndex;
      }  
      return this;
    }
    console.log(arr.shuffle());

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有