js算法：对一个数组进行乱序排序，要求每个元素不会落到原来的位置，且落到其他位置的概率相同

题目

对一个数组进行乱序排序，要求每个元素不会落到原来的位置，且落到其他位置的概率相同。

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

思路

对于乱排：使用随机数得到与当前位置交换的下标，不能是当前位置

防止重复：假设1与2换，2与3换，3与1换，那么会就出现1“换到了原位”的情况。这里我们使用一个flag标记，来记录后面的被交换过的位置，这个位置是不能再交换的。如1与2换，那么2号位就不能再交换（主要是防止2与后面的换了，后面的又与1换了），即使3与1换，得到的结果是：3 1 2，也不会有数字换到原位。

代码

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
function randerArr(arr) {
    // 浅拷贝
    let newArr = arr.slice(0),flag=[],n=arr.length

    for(let i=0;i<n;i++){
        // 如果这个下标之前被交换过则不再交换，防止重复
        if(flag[i]) continue;

        let temp=parseInt(Math.random()*n)
        while(temp===i) temp=parseInt(Math.random()*n)
        // 标记交换过的
        flag[i]=true
        flag[temp]=true
        // 交换
        let swap=newArr[i]
        newArr[i]=newArr[temp]
        newArr[temp]=swap
    }
    return newArr
}
console.log(randerArr(arr));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这里的let newArr = arr.slice(0)是浅拷贝，直接let newArr = arr是深拷贝：修改arr或newArr都会使两边的数组发生改变。

参考：https://blog.csdn.net/qq_44697303/article/details/115438843