洗牌算法

洗牌算法

給定一個n個數的序列，設計一個算法將其隨機打亂，保證每個數出現在任意一個位置的概率相同（也就是說在n!個的排列中，每一個排列出現的概率相同）。

樸素的做法：

假設輸入為數組num[length]。

隨機選一個數，放到num[0]中，再隨機選數，如果該數已經選過，重新選，直到該數未選過時放入num[1]中，以此類推，直到所有的數都選出來，很明顯，這種選法一共有n!中可能，每種可能出現的概率都相同。

但是該做法效率不高，因為選過的數再選將耗費大量時間。

改進的洗牌算法：

基于以上算法的缺陷，我們做出改進：選過的數將不再考慮。比如num[0…k]為已選的數，那么我們的隨機只在k+1到length-1間進行。

void MySwap(int &a, int &b)
{
    int tmp = x;
    x = y;
    y = tmp;
}

void Shuffle(int num[], int length)
{
    if (NULL == num || length <= 0) return;
    for (int index = length-1; index >= 1; --index)
    {
        MySwap(num[index], num[rand()%(index+1)]);
    }
}

解釋一下：

index為本次選的牌的存放位置，rand()%(index+1)產生0到index之間的隨機數，而已選的數的下標為index+1到length-1，所以可以保證已選的數不會再重復選到。

一些小細節：

習慣使用–index而不是index–的原因是：index–需要一個臨時變量來保存自減前的index值，而–index，直接先自減，之后返回自身，因此效率更高一些。（當然，實際上編譯器可能會做一些優化，使得兩者的區別不大，這僅僅是一個良好的編程習慣）。

使用逆序：rand()%(index+1)比較方便地產生0到index之間的隨機數，如果是正序，則需要寫成：

    for (int index = 0; index < length; ++index)
    {
        MySwap(num[index], num[index+rand()%(length-index)]);
    }

運算多一些，而且不夠簡潔。

最后提一個點：以上代碼每次運算的結果都會是一樣的，如果想要每次都不一樣，需要添加種子（使用srand((int)time(0));根據時間來選擇種子）。

每天進步一點點，Come on！
(●’?’●)

本人水平有限，如文章內容有錯漏之處，敬請各位讀者指出，謝謝！