JavaScript洗牌算法深度解析：从抽牌、换牌到插牌的优化演进

作者：木棉时间：2026-10-28 12:13:28浏览：336

本文深入分析JavaScript中实现数组随机排序的洗牌算法。通过对比抽牌法、换牌法和插牌法三种思路，揭示传统实现中的性能瓶颈与随机性偏差问题。重点讲解了如何利用数组末尾元素填补空位或原地交换的方式，将时间复杂度优化至O(n)，并验证了优化后算法的均匀随机性，适用于音乐播放、游戏排序等场景。

洗牌算法是处理随机问题的经典案例，广泛应用于游戏发牌、列表随机排序等场景。其核心目标可以抽象为：生成一个包含M以内所有自然数的随机顺序数组。

在搜索引擎中查询“洗牌算法”，部分早期资料（如某些文库文档）的内容存在误导性，甚至建议使用链表替代数组。这种优化仅具有有限意义，因为链表虽然避免了数组删除元素的移动开销，却引入了额外的读取效率损失，并非最佳方案。

文中提到的第一种方法可概括为“抽牌法”：随机抽取一张牌放入新数组，若再次抽到已被移除的空位，则重新抽取。这种机制导致后续抽取到空位的概率逐渐增大，显然不符合均匀随机的要求。对此，一个直观的优化是：抽走牌后直接减少数组有效长度，而非保留空位。

具体实现如下：

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;
}

除了抽牌思路，还可以采用“换牌法”。部分资料建议“随机交换两个位置，共交换n次（n越大越接近随机）”，这种做法存在缺陷。即使交换次数很大（例如10张牌交换10次），仍可能存在某些牌从未被交换的情况，导致分布不均。对此稍作调整：遍历数组，将第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>

JS算法：洗牌算法(shuffle)

1、洗牌算法

洗牌（随机）算法具有广泛的应用场景，例如音乐播放器的随机播放模式、棋牌游戏中的洗牌逻辑、扫雷游戏中地雷位置的随机分布等，均依赖于该算法。

基本思路：

从原始数组中每次随机选取一个元素，将其放入新数组。每次取出元素后，使用splice方法将其从原数组中移除，使原数组长度减一。

2、JavaScript实现

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]));

JS算法：洗牌算法(shuffle)

至此，关于JavaScript洗牌算法的深入分析介绍完毕。如需了解更多相关技术内容，请查阅本站往期文章或继续关注后续更新。感谢大家的支持！

作者最新文章

JavaScript怎么准确判断数据类型：typeof、instanceof与Object.prototype.toString

2026-11-05 17:09:21

JS中将数组和对象混合组装为JSON字符串

2026-11-05 16:41:42

JS运算符优先级与结合性的区别是什么？

2026-11-05 13:22:02

JS Map怎么只遍历Key或Value

2026-11-05 13:00:36

D3.js 与 ECharts 选型对比：灵活性 vs 开发效率

2026-11-05 09:45:01