js 随机数 洗牌算法

function shuffle(arr){
    var len = arr.length;
    for(var i = 0;i<len -1;i++)
    {
        var idx = Math.floor(Math.random() * (len - 1));
     console.log("idx",idx);
var temp = arr[idx];
console.log("temp",temp); arr[idx]
= arr[len - i - 1];
     console.log("arr[idx]",arr[idx]); arr[len
- i - 1] = temp;
console.log("arr[len - i - 1]",arr[len - i - 1]) }
return arr; }

Knuth-Durstenfeld Shuffle

Fisher-Yates 洗牌算法的一个变种是 Knuth Shuffle

每次从未处理的数组中随机取一个元素,然后把该元素放到数组的尾部,即数组的尾部放的就是已经处理过的元素,这是一种原地打乱的算法,每个元素随机概率也相等,时间复杂度从 Fisher 算法的 O(n2)提升到了 O(n)

  1. 选取数组(长度n)中最后一个元素(arr[length-1]),将其与n个元素中的任意一个交换,此时最后一个元素已经确定
  2. 选取倒数第二个元素(arr[length-2]),将其与n-1个元素中的任意一个交换
  3. 重复第 1 2 步,直到剩下1个元素为止
function shuffle(arr){
    var length = arr.length,
        temp,
        random;
    while(0 != length){
        random = Math.floor(Math.random() * length)
        length--;
        // swap
        temp = arr[length];
        arr[length] = arr[random];
        arr[random] = temp;
    }
    return arr;
}

ES6

Knuth-Durstenfeld shuffle 的 ES6 实现,代码更简洁

function shuffle(arr){
    let n = arr.length, random;
    while(0!=n){
        random =  (Math.random() * n--) >>> 0; // 无符号右移位运算符向下取整
        [arr[n], arr[random]] = [arr[random], arr[n]] // ES6的结构赋值实现变量互换
    }
    return arr;
}
原文地址:https://www.cnblogs.com/CyLee/p/5964520.html