大家好砰诵，我是IT修真院深圳分院第02期學(xué)員，一枚正直善良的web程序員捌显。
今天給大家分享一下茁彭，修真院官網(wǎng)JS任務(wù)02，深度思考中的知識點——洗牌算法具體指的是什么扶歪？
1.背景介紹
洗牌算法理肺，顧名思義摄闸，它的產(chǎn)生是用來解決類似洗牌這種場景的問題的，目的是產(chǎn)生一串等概率的隨機列妹萨，使得很難去預(yù)測牌的順序年枕，洗牌算法是我們常見的隨機問題，在玩游戲乎完，隨機排序時經(jīng)常用到熏兄。同時它也是一道經(jīng)典的面試題。
2.知識剖析
何為洗牌算法树姨？
一個1到n的序列摩桶，隨機打亂，保證每個數(shù)出現(xiàn)在任意一個位置的概率相同帽揪。
3.常見問題
有哪些實現(xiàn)洗牌的算法硝清？
4.解決方案
Fisher-Yates Shuffle ??鏈接
一般化方法
假如要洗牌，那么最隨機的做法無疑是從牌堆里隨便抽一張出來转晰，然后放在一邊芦拿，之后從剩下的牌里重復(fù)之前的操作，直到所有牌都被抽出來放到了另一堆中挽霉。抽象到代碼世界防嗡，按相同的做法，就是隨機從數(shù)組里取出一個元素侠坎，保存到另一個數(shù)組蚁趁，然后重復(fù)之，直到原數(shù)組中所有元素都處理掉实胸。
缺點：即使一個序號上的元素已經(jīng)被處理過了他嫡，由于隨機函數(shù)產(chǎn)生的數(shù)是隨機的，所有這個被處理過的元素序號可能在之后的循環(huán)中不斷出現(xiàn)庐完。
改進方法
處理完一個元素后钢属，我們用Array的splice()方法將其從目標數(shù)組中移除同時也更新了目標數(shù)組的長度，如此一來下次遍歷的時候是從新的長度開始门躯，不會重復(fù)處理的情況了淆党。
缺點：因為調(diào)用splice來刪除數(shù)組元素會導(dǎo)致刪除位置之后的所有元素要做shift操作來向前補充，從而達到將數(shù)組長度減小的目的讶凉，當然這是在后臺自動完成的染乌，但這無疑增加了算法的復(fù)雜度。
算法能否再次優(yōu)化懂讯？
考慮不創(chuàng)建新的數(shù)組來保存已經(jīng)抽取的元素:隨機從數(shù)組中抽出一個元素荷憋，然后與最后個元素交換，相當于把這個隨機抽取的元素放到了數(shù)組最后面去褐望，表示它已經(jīng)是被隨機過了勒庄，同時被換走的那個元素跑到前面去了串前，會在后續(xù)的重復(fù)操作中被隨機掉。一輪操作過后实蔽，下一輪我們只在剩下的n-1個元素也就是數(shù)組的前n-1個元素中進行相同的操作荡碾，直到進行到第一個。
5.編碼實戰(zhàn)
6.擴展思考
除了洗牌算法局装，還有哪些經(jīng)典的排序算法玩荠？
7.參考文獻
參考一：由亂序播放說開了去-數(shù)組的打亂算法Fisher–Yates Shuffle
參考二：UC面試題-完美洗牌算法
8.更多討論
還有沒有更簡單的洗牌算法？
9.視頻資料
今天的分享就到這里啦贼邓，歡迎大家點贊、轉(zhuǎn)發(fā)闷尿、留言塑径、拍磚~
下期不見不散~
