Fe-interview: [js] 第90天 写个方法随机打乱一个数组

[haizhilin2013]

第90天 写个方法随机打乱一个数组

[ghost]

两个思路

• 随机交换

function shuffle(arr) {
    arr.forEach((_, idx) => {
        const targetIdx = Math.floor(Math.random() * arr.length)
        ;[arr[idx], arr[targetIdx]] = [arr[targetIdx], arr[idx]]
    })
    return arr
}

shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
// => [6, 4, 1, 8, 5, 2, 10, 9, 3, 7] or else

• 打乱下标（慢了 300-1000 倍左右）

function shuffleSubscript(n) {
    const arr = new Array(n)
    for (let i = 0; i < n; i++) {
        let val
        do val = Math.floor(Math.random() * n)
        while (arr.includes(val))
        arr[i] = val
    }
    return arr
}

function shuffle(arr) {
    return shuffleSubscript(arr.length).map(s => arr[s])
}

shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
// => [7, 4, 5, 8, 6, 3, 1, 2, 10, 9] or else

[liuxiaole]

懒人版：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].sort(() => Math.random() - 0.5)

[ghost]

@liuxiaole
您好！
这个方法并不是一个很好的打乱实现，它导致每个元素仍有很大的可能在原位附近。
见：https://blog.oldj.net/2017/01/23/shuffle-an-array-in-javascript/#comment-1466

[Konata9]

这题和 Day24 的重复了

https://github.com/haizlin/fe-interview/issues/84

[xxf1996]

function randomArr (arr) {
  let idx = arr.map((item, i) => i)
  let res = []

  for (let i = 0; i < arr.length; i++) {
    let randomIdx = Math.floor(Math.random() * idx.length)
    res.push(arr[idx[randomIdx]])
    idx.splice(randomIdx, 1)
  }

  return res
}

写的可能比较直白，没考虑复杂度；

[cmw-good]

这个改变了原数组
arr.sort(() => {
return Math.random() - 0.5;
}

[JiangXue93]

稍微考虑了下输入验证

function shuffle(arr) {
    if(!arr instanceof Array) {
        return []
    }
    const size = arr.length
    let tmpArr = [...arr]
    for(let i = 0; i <= size - 1; i++ ){
        const position = Math.floor(Math.random() * size)
        [tmpArr[i], tmpArr[position]] =[ tmpArr[position], tmpArr[i]]
    }
    return tmpArr
}

[tonyChenHey]

function rangArr(temparr){  //按下标打乱最佳,数组元素不一定为数字
        var arr_size = temparr.length;
        var new_arr = [];
        var old_arr = [];   //旧下标
        //确保每个元素不在原来的数组位置上 这样就有点乱了
        //让元素失去旧的相邻关系,如之前为[1,4,3],若为[4,3,1],则4,3之间还是相邻的,[3,1,4]这样就很乱了(第二步未实现)
        for(var i = 0;i < arr_size;i++){
            var temp_index; //随机下标
            //找不是当前位置的下标是否可以优化,感觉很low
            do{
                temp_index = Math.floor(Math.random() * arr_size);
            }while (temp_index == i || old_arr.indexOf(temp_index) != -1)
            old_arr.push(temp_index);
            new_arr[i] = temparr[temp_index];
        }
        return new_arr;
    }

    console.log(rangArr([2,5,86,7,11,4,3]))

好像没写对....运行刷新多几遍就卡了

[HuoXiaoYe]

class shuffle {
    constructor(arr) {
        this.oldArrLength = arr.length;
        his.newArr = arr;
        this._init()
    }
    _init() {
        let j = this.oldArrLength / 2;
        for (let i = 0; i <= j; i++) {      
            var randomNum = this._getRandomIndex(this.oldArrLength/ 2 -1 , this.oldArrLength);
            [this.newArr[i],this.newArr[randomNum]] = [this.newArr[randomNum],this.newArr[i]]
         }
    }
    _getRandomIndex(max, min) {
        return Math.floor(Math.random() * (max - min + 1) + min)
    }
}
var myarr = new shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
console.log(myarr.newArr) //[6, 7, 1, 2, 10, 5, 4, 8, 9, 3]

我感觉可以让前面的数字和后面的数字 交换顺序 ， 不过这样效果应该不是很好

[yjua]

洗牌算法

function shuffle(arr) {
    let shuffled = arr.concat(), rand;
    for (let i = shuffled.length; i--;) {
        rand = Math.floor(Math.random() * (i + 1));
        [shuffled[i],shuffled[rand]] = [shuffled[rand],shuffled[i]] 
    }
    return shuffled;
}

[liuxiaole]

@t532 谢谢告知。第一直觉是没问题啊这个这么简单，仔细想了一下，确实是存在问题的，具体问题由 sort 的实现不同而不同。以快排为例，第一次做 partition 时会固定下一个中间数，这个数有很大概率落在中间，有极小概率落在两端。 https://bost.ocks.org/mike/shuffle/compare.html 这里可以看到不同洗牌算法是否真的洗乱，可以看到 random compareFn 的实现在三个角上有大量颜色。

[kjhghuj]

@t532 老哥，第一种方法中的那个；号是啥呀？我自己试着写，不加；号就报错.....

[ghost]

@kjhghuj

老哥，第一种方法中的那个；号是啥呀？我自己试着写，不加；号就报错.....

你好，不加分号则js引擎将后一个结构赋值运算符的 = 前部分解释为成员访问。

[forever-z-133]

function shuffle(arr) {
  arr = arr.slice(0);
  var newArr = new Array(arr.length);
  while (arr.length) {
    var rdm = Math.random() * arr.length >> 0;
    newArr[arr.length - 1] = arr.splice(rdm, 1)[0];
  }
  return newArr;
}
console.log(shuffle([1,2,3,4,5,6,7,8,9]));

没有人写 while 循环，感觉应该也是个比较烧性能的。

[Konata9]

/**

• 写个方法随机打乱一个数组
• 关联题目 Day24
  */

//洗牌算法在随机性上会更好一些
const shuffle = (arr) => {
if (!Array.isArray(arr)) {
return;
}

const len = arr.length;
if (len === 0) {
return arr;
}

for (let i = 0; i < len; i++) {
const randomIndex = Math.floor(Math.random() * len);
[arr[i], arr[randomIndex]] = [arr[randomIndex], arr[i]];
}

return arr;
};

// 利用 sort 结合 Math.random 方法在数组长度过长时随机效果会不好
arr.sort(() => (Math.random() > 0.5 ? 1 : -1));

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
console.log(shuffle(arr));

[viccowang]

Fisher-Yates 洗牌随机数组排列

function shuffle (arr) {
  let l = arr.length
  while (l) {
        let index = Math.floor(Math.random() * l--);
        let cur = arr[l];
        arr[l] = arr[index];
        arr[index] = cur;
  }
  return arr
}

console.log(  shuffle(arr) )