快捷導(dǎo)航

javascript隨機之洗牌算法深入分析

更新時間：2023年11月17日 23:24:49 投稿：junjie

這篇文章主要介紹了javascript隨機之洗牌算法深入分析,同時提供了一個完整實例,需要的朋友可以參考下

洗牌算法是我們常見的隨機問題，在玩游戲、隨機排序時經(jīng)常會碰到。它可以抽象成這樣：得到一個M以內(nèi)的所有自然數(shù)的隨機順序數(shù)組。

在百度搜“洗牌算法”，第一個結(jié)果是《百度文庫-洗牌算法》，掃了一下里面的內(nèi)容，很多內(nèi)容都容易誤導(dǎo)別人走上歧途，包括最后用鏈表代替數(shù)組，也只是一個有限的優(yōu)化（鏈表也引入了讀取效率的損失）。

該文里的第一種方法，可以簡單描述成：隨機抽牌，放在另一組；再次抽取，抽到空牌則重復(fù)抽。
“抽到空牌則重復(fù)抽”這會導(dǎo)致后面抽到空牌的機會越來越大，顯然是不合理的。
可以優(yōu)化一步成：牌抽走后，原牌變少。（而不是留下空牌）

代碼如下：

function shuffle_pick_1(m) //洗牌 //抽牌法
{
    //生成m張牌
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
        arr[i] = i;
    }

    //每次抽出一張牌，放在另一堆。因為要在數(shù)組里抽出元素，把后面的所有元素向前拉一位，所以很耗時。
    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;
}

這個也明顯有問題，因為數(shù)組如果很大的話，刪除中間的某個元素，會導(dǎo)致后面的排隊向前走一步，這是一個很耗時的動作。
回想一下“我們?yōu)槭裁匆獎h除那個元素？”目的就是為了不產(chǎn)生空牌。
除了刪除那個元素之外，我們是不是還有其它方式來去除空牌？
----有的，我們把最后一張未抽的牌放在那個抽走的位置上就可以了。
所以，這個思路我們可以優(yōu)化成這樣：

function shuffle_pick(m) //洗牌 //抽牌法優(yōu)化牌
{
    //生成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越大，越接近隨機”。
這個做法是不對的，就算n很大（例如10張牌，進(jìn)行10次調(diào)換），也還存在很大可能“有的牌根本沒換位置”。
順著這個思路，做一點小調(diào)整就可以了：第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) //洗牌 //插牌法
{
    //每次生成一張最大的牌，插在隨機的某張牌前。因為要在數(shù)組里插入元素，把后面的所有元素向后擠一位，所以很耗時。
    var arr = [0];
    for (var i=1; i<m; i++) {
        arr.splice(Math.floor(Math.random()*(i+1)),0,i);
    }
    return arr;
}

以上的代碼也會有一些問題：就是隨著牌數(shù)的增多，插牌變得越來越困難，因為插牌會導(dǎo)致后面的很多牌都往后推一步。
當(dāng)然，我們也可以適當(dāng)?shù)膬?yōu)化一下：先有n-1張牌，第n張牌放在最后，然后與任意一張牌互換位置。

代碼如下：

function shuffle_insert(m) //洗牌 //插牌法優(yōu)化版，可以用數(shù)學(xué)歸納法證明，這種洗牌是均勻的。
{
    //每次生成一張最大的牌，與隨機的某張牌換位子
    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;
}

好的，全部的代碼如下，有興趣的同學(xué)可以在自己的機器上試下，看下他們各自的執(zhí)行效率、以及最后的結(jié)果是否是理論隨機。

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

??? //每次抽出一張牌，放在另一堆。因為要在數(shù)組里抽出元素，把后面的所有元素向前拉一位，所以很耗時。
??? 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) //洗牌 //抽牌法優(yōu)化牌
{
??? //生成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) //洗牌 //插牌法
{
??? //每次生成一張最大的牌，插在隨機的某張牌前。因為要在數(shù)組里插入元素，把后面的所有元素向后擠一位，所以很耗時。
??? 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) //洗牌 //插牌法優(yōu)化版，可以用數(shù)學(xué)歸納法證明，這種洗牌是均勻的。
{
??? //每次生成一張最大的牌，與隨機的某張牌換位子
??? 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 = ["抽牌", "抽牌優(yōu)化", "換牌", "插牌", "插牌優(yōu)化"]
??? 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、洗牌算法

洗牌(隨機)算法有很多應(yīng)用，例如我們平時用的音樂播放器隨機播放，棋牌游戲中的洗牌，掃雷游戲中雷的位置隨機等等，都會用到洗牌算法。

思路：

從原始數(shù)組中每次隨機選中一個元素，然后放入新數(shù)組中，每取出一個元素后，將將它從原數(shù)組中取出（使用splice方法），原數(shù)組長度減一。

2、JavaScript實現(xiàn)

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