欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

关于洗牌算法的错误认识

程序员文章站 2022-07-04 23:12:35
下面是我之前一直使用的一个洗牌算法: 但仔细想想,其实这是非常不合理的,因为已经交换过的位置,下次仍然可能会被选上。 比较好的做法是排除已经交换过的位置,将剩下的位置洗牌,如下: ......

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

    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());