javascript隨機之洗牌演算法深入分析_javascript技巧

洗牌演算法是我們常見的隨機問題，在玩遊戲、隨機排序時常常會碰到。它可以抽象化成這樣：得到一個M以內的所有自然數的隨機順序數組。

在百度搜“洗牌演算法”，第一個結果是《百度文庫-洗牌演算法》，掃了一下裡面的內容，很多內容都容易誤導別人走上歧途，包括最後用鍊錶代替數組，也只是一個有限的最佳化（鍊錶也引入了讀取效率的損失）。

該文裡的第一種方法，可以簡單描述成：隨機抽牌，放在另一組；再次抽取，抽到空牌則重複抽。
「抽到空牌就重複抽」這會導致後面抽到空牌的機會越來越大，顯然是不合理的。
可以優化一步成：牌抽走後，原牌變少。 （而不是留下空牌）
代碼如下：

複製代碼 代碼如下:

代碼如下:


function shuffle_pick_1(m) //洗牌//抽牌法
{
    //產生m張牌    var arr = new Array(m);

    var arr = new Array(m);
    var arr = new Array(m);
 ; i        arr[i] = i;
    }

    //每次都抽出一張牌，放在另一堆。因為要在陣列裡抽出元素，把後面的所有元素向前拉一位，所以很耗時。
    var arr2 = new Array();
    for (var i=m; i>0; i--) {
        var id = Math.floor(Math.random()*); 🎜>        arr2.push(arr[rnd]);

        arr.splice(rnd,1);    }

    return arr2;
}

這個也明顯有問題，因為陣列如果很大的話，刪除中間的某個元素，會導致後面的排隊向前走一步，這是一個很耗時的動作。

回想一下「我們為什麼要刪除那個元素？」目的就是為了不產生空牌。

除了刪除那個元素之外，我們是不是還有其它方式來去除空牌？ ----有的，我們把最後一張未抽的牌放在那個抽走的位置上就可以了。 所以，這個思路我們可以優化成這樣：

複製程式碼


代碼如下:


function shuffle_pick(m) //洗牌/抽吸>卡法最佳化牌
{    //產生m張牌

    var arr = new Array(m);
    [i] = i;
    }

    //每次都抽出一張牌，放在另一堆。把最後一張未抽過的牌放在空位上。
    var arr2 = new Array();
    for (var i=m; i>0;) {
        var .push(arr[rnd]);
        arr[rnd] = arr[--i];
    }

    return arr2;《百度文庫-洗牌演算法》提到一種換牌想法：「隨機交換兩個位置，共交換n次，n越大，越接近隨機」。
這個做法是不對的，就算n很大（例如10張牌，進行10次調換），也還存在很大可能「有的牌根本沒換位置」。
順著這個思路，做一點小調整就可以了：第i張與任一張牌換位子，換完一輪即可。
程式碼如下：

複製程式碼 程式碼如下:

function shuffle_swap(>

function shuffle_swap(m) //洗牌/卡法
{
    //產生m張牌
    var arr = new Array(m);
    for (var i=0; i    for (var i=0; i    for (var i=0; i   ] = i;
    }

    //第i張與任一牌換位子，換完一輪即可
    for (var i=0; i        vard = Math.floor( rnd = Math.floor( rnd = Math.floor( rnd = Math.floor( rnd = Math.floor( rnd = Math.floor( Math.random()*(i 1)),
            temp = arr[rnd];
         }
    return arr;
}

除了抽牌與換牌的思路，我們還可以用插牌的思路：先有一張牌，第二張牌有兩個位置可隨機插入（第一張牌前，或後），第三張牌有三個位置可隨機插入（放在後面，或插在第一位，或插在第二位），依此類推
代碼如下：

複製程式碼 程式碼如下:

function shuffle_insert_1(m) ///插/插牌法
{
    //每次產生一張最大的牌，插在某張隨機的牌前。因為要在陣列裡插入元素，把後面的所有元素都向後擠一位，所以很耗時。
    var arr = [0];
    for (var i=1; i        arr.splice(Math.floor(Math.random()*(i   arr.splice(Math.floor(Math.random)*(i rand1), 0,i);
    }
    return arr;
}

以上的程式碼也會有一些問題：就是隨著牌數的增多，插牌變得越來越困難，因為插牌會導致後面的很多牌都往後推一步。
當然，我們也可以適當的優化一下：先有n-1張牌，第n張牌放在最後，然後與任一張牌互換位置。
程式碼如下：

複製程式碼 程式碼如下:

function shuffle_insert(m) //洗牌/插牌法最佳化版，可以用數學歸納法證明，這種洗牌是均勻的。
{
    //每次產生最大的牌，以隨機的某張牌換位子
    var arr = new Array(m);
    arr[0] = 0;
    for (var i=1; i        var i=1; i        var i=1; i        var i=1; i        var i=1; i        var i=1; i        var i=1; i        vari>  ;

        arr[rnd] = i;    }

    return arr;

}

好的，全部的程式碼如下，有興趣的同學可以在自己的機器上試下，看下他們各自的執行效率、以及最後的結果是否是理論隨機。  

複製程式碼 程式碼如下: