search
尋找貓咪~QQ 地點 桃園市桃園區 Taoyuan , Taoyuan

三種洗牌演算法簡介 – jashliao部落格

三種洗牌演算法簡介


資料來源: 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==&devicetype=Windows+10+x64&version=6300002f&lang=zh_TW&exportkey=ArX9e8vuE7SIwUTbxf7KqhU=&pass_ticket=69FsYssrwJr5C/lz3cYShD/HwWReRFqmI4Zx2zlJq9ergFro/sgaTeTB7xbvrG6y&wx_header=0


01.Fisher-Yates Shuffle  

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

void  Fisher_Yates_Shuffle(vector& arr,vector& res)
{
    srand((unsigned)time(NULL));
    int k;
    for (int i=0;i


02.Knuth-Durstenfeld Shuffle

/*
時間複雜度為O(n),空間複雜度為O(1),缺點必須知道數組長度n。
*/
void  Knuth_Durstenfeld_Shuffle(vector&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&arr,vector& res)
{
    res.assign(arr.size(),0);
    copy(arr.begin(),arr.end(),res.begin());
    int k;
    for (int i=0;i


04.Reservoir Sampling

void Reservoir_Sampling(vector& arr)
{
    int k;
    for (int i=M;i



熱門推薦

本文由 jashliaoeuwordpress 提供 原文連結

寵物協尋 相信 終究能找到回家的路
寫了7763篇文章,獲得2次喜歡
留言回覆
回覆
精彩推薦