Zi 字媒體
2017-07-25T20:27:27+00:00
三種洗牌演算法簡介
資料來源: 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
寫了
5860316篇文章，獲得
23313次喜歡