js如何实现数组随机排序【附洗牌算法心得】

超、凢脫俗 2023-09-29 15:11 6阅读 0赞

**目录**

1.利用数组方法sort实现随机排序

2.洗牌算法实现随机排序

3.洗牌算法深入分析

--------------------

### 1.利用数组方法sort实现随机排序 ###

> **实现随机排序方法还是很多的，用for循环是可以写的，用Lodash等三方js方法库也行。但个人以为使用sort比较方便，但是他又缺点，缺点就是不够那么的随机，我看过sort运行机制后，发现他竟然是利用一个比较器两两比较出来的。**

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

![d9801e6c38d2440c84c268d255207b7d.png][]

--------------------

### 2.洗牌算法实现随机排序 ###

> **从原始数组中每次随机选中一个元素，然后放入新数组中，每取出一个元素后，将将它从原数组中取出（使用splice方法），原数组长度减一。**
> 
> 举例：
> 
> 现在我有红桃K、黑桃A、小王三张牌，要求打乱顺序，你可以从三张牌抽出任意一张，假设你抽到的是小王，那么我手里三张牌变成两张牌，你手里变成1张牌，以此类推，实现随机排序。

**代码实现：**

function shuffle(array){
        let res = [], random;
        while(array.length>0){
            random = Math.floor(Math.random()*array.length);
            res.push(array[random]);
            array.splice(random, 1);
        }
        return res;
    }
    
    console.log(shuffle([1,2,3,4,5]));

![647c553be6c040f09b510909c22d4c4c.png][]

--------------------

### 3.洗牌算法深入分析 ###

思路：我有一副牌，随机抽取牌，旧的牌数量相应减少!
    
    function shuffle(m) //洗牌 //抽牌法
    {
    //生成m张牌
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
    arr[i] = i;
    }
    //每次抽出一张牌，需要遍历整个数组，所以很耗时。
    var arr2 = new Array();
    for (var i=m; i>0; i–) {
    var rnd = Math.floor(Math.random()*i);
    arr2.push(arr[rnd]);
    arr.splice(rnd,1);
    }
    return arr2;
    }
    但是这样的话，因为数组如果很大的话，删除中间的某个元素，会导致后面的数据被执行，会对性能影响很大。
    我们删除那个元素的目的就是为了不产生空牌。
    除了删除那个元素之外，我们是不是还有其它方式来去除空牌？
    ----------------------------------------------------------------------------------
    只需把最后一张未抽的牌放在那个抽走的位置上就可以了。
    顺着这个思路我们可以优化成这样：
    代码如下:
    function shuffle_pick(m) //洗牌 //抽牌法优化牌
    {
    //生成m张牌
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
    arr[i] = i;
    }
    //每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。
    var arr2 = new Array();
    for (var i=m; i>0;) {
    var rnd = Math.floor(Math.random()*i);
    arr2.push(arr[rnd]);
    arr[rnd] = arr[–i];
    }
    return arr2;
    }
    除了抽牌思路，我们还可以用换牌思路：
    “随机交换两个位置，共交换n次，n越大，越接近随机”。
    ---------------------------------------------------------------------------
    顺着这个思路，做一点小调整就可以了：第i张与任意一张牌换位子，换完一轮即可。
    代码如下:
    function shuffle_swap(m) //洗牌 //换牌法
    {
    //生成m张牌
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
    arr[i] = i;
    }
    //第i张与任意一张牌换位子，换完一轮即可
    for (var i=0; i<m; i++) {
    var rnd = Math.floor(Math.random()*(i+1)),
    temp = arr[rnd];
    arr[rnd] = arr[i];
    arr[i]=temp;
    }
    return arr;
    }
    ------------------------------------------------------------------
    除了抽牌与换牌的思路，我们还可以用插牌的思路：先有一张牌，第二张牌有两个位置可随机插入（第一张牌前，或后），第三张牌有三个位置可随机插入（放在后面，或插在第一位，或插在第二位），依此类推
    代码如下:
    function shuffle_insert_1(m) //洗牌 //插牌法
    {
    //每次生成一张最大的牌，插在随机的某张牌前。因为要在数组里插入元素，把后面的所有元素向后挤一位，所以很耗时。
    var arr = [0];
    for (var i=1; i<m; i++) {
    arr.splice(Math.floor(Math.random()*(i+1)),0,i);
    }
    return arr;
    }
    --------------------------------------------------
    以上的代码也会有一些问题：就是随着牌数的增多，插牌变得越来越困难，因为插牌会导致后面的很多牌都往后推一步。
    当然，我们也可以适当的优化一下：先有n-1张牌，第n张牌放在最后，然后与任意一张牌互换位置。
    代码如下：
    function shuffle_insert(m) //洗牌 //插牌法优化版，可以用数学归纳法证明，这种洗牌是均匀的。
    {
    //每次生成一张最大的牌，与随机的某张牌换位子
    var arr = new Array(m);
    arr[0] = 0;
    for (var i=1; i<m; i++) {
    var rnd = Math.floor(Math.random()*(i+1));
    arr[i] = arr[rnd];
    arr[rnd] = i;
    }
    return arr;
    }
    -------------------------------
    最后是全部代码：
    代码如下:
    <html>
    <head>
    <meta http-equiv=”Content-Type” content=”text/html; charset=gb2312″>
    <title>JK：javascript 洗牌算法 </title>
    </head>
    <body>
    <script type=”text/javascript”>
    function shuffle_pick_1(m) //洗牌 //抽牌法
    {
    //生成m张牌
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
    arr[i] = i;
    }
    //每次抽出一张牌，放在另一堆。因为要在数组里抽出元素，把后面的所有元素向前拉一位，所以很耗时。
    var arr2 = new Array();
    for (var i=m; i>0; i–) {
    var rnd = Math.floor(Math.random()*i);
    arr2.push(arr[rnd]);
    arr.splice(rnd,1);
    }
    return arr2;
    }
    function shuffle_pick(m) //洗牌 //抽牌法优化牌
    {
    //生成m张牌
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
    arr[i] = i;
    }
    //每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。
    var arr2 = new Array();
    for (var i=m; i>0;) {
    var rnd = Math.floor(Math.random()*i);
    arr2.push(arr[rnd]);
    arr[rnd] = arr[–i];
    }
    return arr2;
    }
    function shuffle_swap(m) //洗牌 //换牌法
    {
    //生成m张牌
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
    arr[i] = i;
    }
    //第i张与任意一张牌换位子，换完一轮即可
    for (var i=0; i<m; i++) {
    var rnd = Math.floor(Math.random()*(i+1)),
    temp = arr[rnd];
    arr[rnd] = arr[i];
    arr[i]=temp;
    }
    return arr;
    }
    function shuffle_insert_1(m) //洗牌 //插牌法
    {
    //每次生成一张最大的牌，插在随机的某张牌前。因为要在数组里插入元素，把后面的所有元素向后挤一位，所以很耗时。
    var arr = [0];
    for (var i=1; i<m; i++) {
    arr.splice(Math.floor(Math.random()*(i+1)),0,i);
    }
    return arr;
    }
    function shuffle_insert(m) //洗牌 //插牌法优化版，可以用数学归纳法证明，这种洗牌是均匀的。
    {
    //每次生成一张最大的牌，与随机的某张牌换位子
    var arr = new Array(m);
    arr[0] = 0;
    for (var i=1; i<m; i++) {
    var rnd = Math.floor(Math.random()*(i+1));
    arr[i] = arr[rnd];
    arr[rnd] = i;
    }
    return arr;
    }
    //alert(shuffle_pick(10))
    var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
    funcNames = [“抽牌”, “抽牌优化”, “换牌”, “插牌”, “插牌优化”]
    m = 10000,
    times=[];
    for(var i = 0; i < funcs.length; i++){
    var d0= new Date();
    funcs[i](m);
    funcNames[i] = (new Date() – d0) + ‘\t’ + funcNames[i];
    }
    alert(funcNames.join(‘\n’));
    </script>
    </body>
    </html>

[d9801e6c38d2440c84c268d255207b7d.png]: https://img-blog.csdnimg.cn/d9801e6c38d2440c84c268d255207b7d.png
[647c553be6c040f09b510909c22d4c4c.png]: https://img-blog.csdnimg.cn/647c553be6c040f09b510909c22d4c4c.png