美文网首页
javascript实现乱序数组——洗牌算法

javascript实现乱序数组——洗牌算法

作者: 踏莎行 | 来源:发表于2021-04-21 17:31 被阅读0次

    使用sort()函数实现

    关于sort的使用,可以看这篇内容https://www.jianshu.com/p/80b814871ac7
    sort方法中传入一个函数,

    arr.sort(function(a, b){
        return a - b
    })
    
    return a-b的结果 ab的排序结果
    负数 a排在b之前
    0 不会进行排序
    正数 b排在a的前面

    结合这个函数的特点加上随机数,我们就可以实现一个乱序数组了

        var arr = [1, 2, 3, 4, 5]
        function ramdomArr(a, b){
          return Math.random() - 0.5
        }
        console.log(arr.sort(ramdomArr));
    

    随机数是生成0-1之间的,我们用这个随机数去减0.5就会得到不同的正数和负数,再利用sort方法,就能实现一个乱序数组了。

    Fisher–Yates shuffle洗牌算法

    使用sort实现的乱序貌似是实现了,由于浏览器的对随机数实现机制,这种乱序并非真正意义上的乱序,目前最好的实现方式就是洗牌算法了
    原理
    首先从所有元素中随机选取一个与第一个元素进行交换,然后在第二个之后选择一个元素与第二个交换,直到最后一个元素
    实现一

    var arr = [1, 2, 3, 4, 5]
    var shuffle = function (arr) {
      for (var i = arr.length - 1; i >= 0; i--) {
        var randomIndex = Math.floor(Math.random() * (i + 1));
        var itemAtIndex = arr[randomIndex];
        arr[randomIndex] = arr[i];
        arr[i] = itemAtIndex;
      }
      return arr;
    }
    
    var res = shuffle(arr)
    console.log(res); // (5) [3, 5, 2, 1, 4]
    

    实现二

    var shuffle = function (arr) {
      var newArr = []
      while(arr.length != 0){
        var rand = Math.floor((Math.random() * arr.length))
        newArr.push(arr[rand])
        arr.splice(rand, 1)
      }
      return newArr
    }
    

    相关文章

      网友评论

          本文标题:javascript实现乱序数组——洗牌算法

          本文链接:https://www.haomeiwen.com/subject/cbfwlltx.html