大家好，我是IT修真院鄭州分院第七期的學(xué)員馮亞超要拂，一枚正直純潔善良的WEB程序員 今天給大家分享一下抠璃，洗牌算法具體指的是什么？
一脱惰、背景介紹
洗牌算法(Shuffling Algorithm)搏嗡，顧名思義，它的產(chǎn)生是用來解決類似洗牌這種場(chǎng)景的問題的拉一，目的是產(chǎn)生一串等概率的隨機(jī)列采盒，使得很難去預(yù)測(cè)牌的順序。
什么是好的洗牌算法：
洗牌之后蔚润，如果能夠保證每一個(gè)數(shù)出現(xiàn)在所有位置上的概率是相等的磅氨，那么這種算法是符合要求的；這在個(gè)前提下嫡纠，盡量降低時(shí)間和空間復(fù)雜度烦租。
二、知識(shí)剖析
KNUTH-DURSTENFELD SHUFFLE
其算法思想就是 從原始數(shù)組中隨機(jī)抽取一個(gè)新的元素到新數(shù)組中
1.從還沒處理的數(shù)組中除盏，產(chǎn)生一個(gè)[0, n]之間的隨機(jī)數(shù) random
2.從剩下的n個(gè)元素中把第 random 個(gè)元素取出到新數(shù)組中
3.刪除原數(shù)組第random個(gè)元素
4.重復(fù)第 2 3 步直到所有元素取完
5.最終返回一個(gè)新的打亂的數(shù)組
FISHER–YATES SHUFFLE
每次從未處理的數(shù)組中隨機(jī)取一個(gè)元素叉橱，然后把該元素放到數(shù)組的尾部，即數(shù)組的尾部放的就是已經(jīng)處理過的元素者蠕，這是一種原地打亂的算法赏迟，每個(gè)元素隨機(jī)概率也相等，時(shí)間復(fù)雜度從 Fisher 算法的 O(n2)提升到了 O(n)
1.選取數(shù)組(長(zhǎng)度n)中最后一個(gè)元素(arr[length-1])蠢棱，將其與n個(gè)元素中的任意一個(gè)交換，此時(shí)最后一個(gè)元素已經(jīng)確定
2.選取倒數(shù)第二個(gè)元素(arr[length-2])甩栈，將其與n-1個(gè)元素中的任意一個(gè)交換
3.重復(fù)第 1 2 步泻仙，直到剩下1個(gè)元素為止
INSIDE-OUT ALGORITHM
Knuth-Durstenfeld Shuffle 是一個(gè)in-place算法，原始數(shù)據(jù)被直接打亂量没，有些應(yīng)用中可能需要保留原始數(shù)據(jù)玉转，因此需要開辟一個(gè)新數(shù)組來存儲(chǔ)打亂后的序列。 Inside-Out Algorithm 算法的基本思想是設(shè)一游標(biāo)i從前向后掃描原始數(shù)據(jù)的拷貝殴蹄，在[0, i]之間隨機(jī)一個(gè)下標(biāo)j究抓，然后用位置j的元素替換掉位置i的數(shù)字，再用原始數(shù)據(jù)位置i的元素替換掉拷貝數(shù)據(jù)位置j的元素袭灯。其作用相當(dāng)于在拷貝數(shù)據(jù)中交換i與j位置處的值刺下。
三、常見問題
FISHER–YATES SHUFFLE是如何實(shí)現(xiàn)的稽荧？
四橘茉、解決方案
FISHER–YATES SHUFFLE的JS實(shí)現(xiàn)
Array.prototype.shuffle =function () {
var input =this;
? ? for (var i = input.length -1;i>=0;i--){
var randomIndex = Math.floor(Math.random() * (i +1));
? ? ? ? var itemAtIndex = input[randomIndex];
? ? ? ? input[randomIndex] = input[i];
? ? ? ? input[i] = itemAtIndex;
? ? }
return input;
};
shuffle 函數(shù)掛載在 Array 對(duì)象的原型之下，便于數(shù)組直接調(diào)用該函數(shù)。在 shuffle 函數(shù)內(nèi)部畅卓，this 引用的就是調(diào)用該 shuffle 的數(shù)組擅腰。 用一個(gè)新的變量引用 this，也就是調(diào)用 shuffle 函數(shù)的數(shù)組翁潘。接下來的for循環(huán)用于遍歷所有數(shù)組內(nèi)的所有元素趁冈，并進(jìn)行隨機(jī)交換。 注意拜马，遍歷順序是從后往前進(jìn)行的渗勘，也就是說從 input.length-1 位置的元素開始，直到遍歷到數(shù)組中的第一個(gè)元素一膨。遍歷過程中的位置由變量 i 指定呀邢。 接下來，使用了兩行代碼在指定范圍內(nèi)挑選一個(gè)隨機(jī)元素豹绪。 變量randomIndex存儲(chǔ)了一個(gè)隨機(jī)數(shù)价淌，該隨機(jī)數(shù)可以用作數(shù)組的索引，進(jìn)而提取一個(gè)隨機(jī)元素瞒津。注意蝉衣，該隨機(jī)數(shù)的最大值并不是數(shù)組的長(zhǎng)度，而是變量i的值巷蚪。 確定了隨機(jī)元素的索引之后病毡，用新的變量保存該元素的值，然后交換選中元素和隨機(jī)元素的值屁柏。
五啦膜、編碼實(shí)戰(zhàn)
六、拓展思考
怎么保證這個(gè)算法得到的數(shù)組是完全隨機(jī)的（即等概）淌喻？
使用程序得到的一般是偽隨機(jī)數(shù)
筆者目前了解到最優(yōu)秀的是梅森旋轉(zhuǎn)算法僧家，其在低于623次元的空間以內(nèi)不存在線性回歸，但仍然是一個(gè)偽隨機(jī)算法裸删。
七八拱、參考文獻(xiàn)
http://blog.csdn.net/robinjwong/article/details/18261393
https://www.tuicool.com/articles/qIjqQzb
八、更多討論
還有沒有更簡(jiǎn)單的洗牌算法
理論上來說還是有的,但是目前的主流洗牌算法基本上都屬于這三種思想.
Q1:提問人:王棟?
問題:怎么保證洗牌算法的性能問題Ｑ乃肌稻？？匕荸？
A1:回答人:馮亞超?
回答:性能應(yīng)該是指在最短的時(shí)間內(nèi)讓每一個(gè)元素隨機(jī)的概率都相等,現(xiàn)在沒有絕對(duì)的性能最好的算法,無論哪種算法,都是屬于這三種思想里面的一種.
Q2:提問人:王棟?
問題:我們?cè)谑裁磿r(shí)候會(huì)用到洗牌算法爹谭？？榛搔？
A2:回答人:馮亞超?
回答:比如任務(wù)2的狼人殺游戲,隨機(jī)分配身份;或者音樂播放器的隨機(jī)播放等等.
Q3:提問人:王棟
問題:怎么保證概率相等旦棉？齿风？
A3:回答人:馮亞超?
回答:使用程序得到的一般是偽隨機(jī)數(shù)
筆者目前了解到最優(yōu)秀的是梅森旋轉(zhuǎn)算法，其在低于623次元的空間以內(nèi)不存在線性回歸绑洛，但仍然是一個(gè)偽隨機(jī)算法救斑。
感謝大家觀看！
今天的分享就到這里啦真屯，歡迎大家點(diǎn)贊脸候、轉(zhuǎn)發(fā)、留言绑蔫、拍磚~
獲得更多IT技能运沦，請(qǐng)移步官網(wǎng) 點(diǎn)擊鏈接直達(dá)：http://www.jnshu.com/login/1/17884272
