三種洗牌演算法簡介

資料來源: https://mp.weixin.qq.com/s?__biz=MzI1MTIzMzI2MA==&mid=2650570695&idx=2&sn=c8fb78d14f924608e13f1af1e94422ed&chksm=f1fec944c6894052487bacc6539e2d66cc12a8d87ff84047f8921b68b6661d741e32b6243c87&scene=126&sessionid=1608688583&key=c2a9e1610510457867b0112ebdaa161ed33a9daa3957c4fb7ffcc5f2e6c6fc3c0646132e9ae409e21e1ca39e84e884712aa823f58664d5d5032b56d6bc3b88251963e685206eaa2a2d61f20dd070076526cbab4f27557371e3f58e3a8805ee9ea594a6534a745f6efa177c1a4f545237aa56a303c972ee3d412e602678165110&ascene=1&uin=MjIwODk2NDgxNw%3D%3D&devicetype=Windows+10+x64&version=6300002f&lang=zh_TW&exportkey=ArX9e8vuE7SIwUTbxf7KqhU%3D&pass_ticket=69FsYssrwJr5C%2Flz3cYShD%2FHwWReRFqmI4Zx2zlJq9ergFro%2FsgaTeTB7xbvrG6y&wx_header=0

01.Fisher-Yates Shuffle  

/*
時間複雜度為O(n*n),空間複雜度為O(n)。
*/
#define N 10
#define M 5

void  Fisher_Yates_Shuffle(vector<int>& arr,vector<int>& res)
{
    srand((unsigned)time(NULL));
    int k;
    for (int i=0;i<M;++i)
    {
       k=rand()%arr.size();
       res.push_back(arr[k]);
       arr.erase(arr.begin()+k);
    }
}

02.Knuth-Durstenfeld Shuffle

/*
時間複雜度為O(n),空間複雜度為O(1),缺點必須知道數組長度n。
*/
void  Knuth_Durstenfeld_Shuffle(vector<int>&arr)
{
    for (int i=arr.size()-1;i>=0;--i)
    {
        srand((unsigned)time(NULL));
        swap(arr[rand()%(i+1)],arr[i]);
    }  
}

03.Inside-Out Algorithm

/*
時間複雜度為O(n),空間複雜度為O(n)。
*/
void Inside_Out_Shuffle(const vector<int>&arr,vector<int>& res)
{
    res.assign(arr.size(),0);
    copy(arr.begin(),arr.end(),res.begin());
    int k;
    for (int i=0;i<arr.size();++i)
    {
        srand((unsigned)time(NULL));
        k=rand()%(i+1);
        res[i]=res[k];
        res[k]=arr[i];
    }
}

04.Reservoir Sampling

void Reservoir_Sampling(vector<int>& arr)
{
    int k;
    for (int i=M;i<arr.size();++i)
    {
        srand((unsigned)time(NULL));
        k=rand()%(i+1);
        if (k<M)
            swap(arr[k],arr[i]);
    }  
}