1.背景介紹
洗牌算法是我們常見(jiàn)的隨機(jī)問(wèn)題摸吠，在玩游戲、隨機(jī)排序時(shí)經(jīng)常會(huì)碰到嚎花，本質(zhì)是讓一個(gè)數(shù)組內(nèi)的元素隨機(jī)排列寸痢。 類(lèi)似于洗牌，將所有牌的位置打亂紊选，讓他們隨機(jī)出現(xiàn)在任何位置啼止。
2.知識(shí)剖析
常見(jiàn)的洗牌算法
方法一：
假如你要洗牌，那么最隨機(jī)的做法無(wú)疑是從牌堆里隨便抽一張出來(lái)兵罢，然后放在一邊献烦，之后從剩下的牌里重復(fù)之前的操作，直到所有牌都被抽出來(lái)放到了另一堆中趣些。抽象到代碼世界仿荆，按相同的做法，就是隨機(jī)從數(shù)組里取出一個(gè)元素坏平，保存到另一個(gè)數(shù)組拢操，然后重復(fù)之，直到原數(shù)組中所有元素都處理掉舶替。
function shuffle(array) {
? ? var copy = [],
? ? ? ? n = array.length,
? ? ? ? i;
? ? // 如果還剩有元素則繼續(xù)令境。。顾瞪。
? ? while (n) {
? ? ? ? // 隨機(jī)抽取一個(gè)元素
? ? ? ? i = Math.floor(Math.random() * array.length);
? ? ? ? // 如果這個(gè)元素之前沒(méi)有被選中過(guò)舔庶。。
? ? ? ? if (i in array) {
? ? ? ? ? ? copy.push(array[i]);
? ? ? ? ? ? delete array[i];
? ? ? ? ? ? n--;
? ? ? ? }
? ? }
? ? return copy;
}
方法二：
方法一的問(wèn)題在此陈醒，即使一個(gè)序號(hào)上的元素已經(jīng)被處理過(guò)了惕橙，由于隨機(jī)函數(shù)產(chǎn)生的數(shù)是隨機(jī)的，所有這個(gè)被處理過(guò)的元素序號(hào)可能在之后的循環(huán)中不斷出現(xiàn)钉跷，一是效率問(wèn)題弥鹦，另一個(gè)就是邏輯問(wèn)題了，存在一種可能是永遠(yuǎn)運(yùn)行不完爷辙！
所以改進(jìn)的做法就是處理完一個(gè)元素后彬坏，我們用Array的splice()方法將其從目標(biāo)數(shù)組中移除同時(shí)也更新了目標(biāo)數(shù)組的長(zhǎng)度，如此一來(lái)下次遍歷的時(shí)候是從新的長(zhǎng)度開(kāi)始膝晾，不會(huì)重復(fù)處理的情況了栓始。
function shuffle(array) {
? ? var copy = [],
? ? ? ? n = array.length,
? ? ? ? i;
? ? // 如果還剩有元素。血当。? ? while (n) {
? ? ? ? // 隨機(jī)選取一個(gè)元素? ? ? ? i = Math.floor(Math.random() * n--);
? ? ? ? // 移動(dòng)到新數(shù)組中? ? ? ? copy.push(array.splice(i, 1)[0]);
? ? }
? ? return copy;
}
最終版：
上面的做法已經(jīng)可以了幻赚，但上面的改進(jìn)依然還有提升空間禀忆。注意到我們要做的僅僅是將數(shù)組元素重新排序，已經(jīng)取出來(lái)的元素和剩下的元素之和一定是等于數(shù)組原來(lái)的總元素個(gè)數(shù)的坯屿。所以可以考慮不創(chuàng)建新的數(shù)組來(lái)保存已經(jīng)抽取的元素油湖，可以這樣，隨機(jī)從數(shù)組中抽出一個(gè)元素领跛，然后與最后個(gè)元素交換乏德，相當(dāng)于把這個(gè)隨機(jī)抽取的元素放到了數(shù)組最后面去，表示它已經(jīng)是被隨機(jī)過(guò)了吠昭，同時(shí)被換走的那個(gè)元素跑到前面去了喊括，會(huì)在后續(xù)的重復(fù)操作中被隨機(jī)掉。一輪操作過(guò)后矢棚，下一輪我們只在剩下的n-1個(gè)元素也就是數(shù)組的前n-1個(gè)元素中進(jìn)行相同的操作郑什，直到進(jìn)行到第一個(gè)。
Array.prototype.shuffle = function() {
? ? var input = this;
? ? for (var i = input.length - 1; i >= 0; i--) {
? ? ? var randomIndex = Math.floor(Math.random() * (i + 1));//獲取小于this.length的隨機(jī)整數(shù)? ? ? var itemAtIdex = input[randomIndex];
? ? ? input[randomIndex] = input[i];
? ? ? input[i] = itemAtIdex;//input[randomIndex]和input[i]交換值? ? }
? ? return input;
? }
3.常見(jiàn)問(wèn)題
有沒(méi)有簡(jiǎn)潔點(diǎn)的洗牌算法蒲肋？
4.解決方案
arr.sort(function(){ return 0.5-Math.random()});
結(jié)合數(shù)組自帶的sort()方法編寫(xiě),中間變量以及值交換什么的都省了,一行代碼就可以實(shí)現(xiàn)蘑拯，相對(duì)而言比較簡(jiǎn)單，但是他并不能實(shí)現(xiàn)真正意義的隨機(jī)兜粘。
var arr = [0,1,2,3,4,5,6,7,8,9];var res = [0,0,0,0,0,0,0,0,0,0];var t = 10000;for(var i = 0; i < t; i++){
? var sorted = shuffle(arr.slice(0));
? sorted.forEach(function(o,i){
? ? ? res[i] += o;
? });
}
res = res.map(function(o){
? ? return o / t;
});console.log(res);
5.編碼實(shí)戰(zhàn)
6.擴(kuò)展思考
怎么保證這個(gè)算法得到的數(shù)組是完全隨機(jī)的（即等概）申窘？
計(jì)算機(jī)本來(lái)就沒(méi)辦法實(shí)現(xiàn)真正的隨機(jī)，計(jì)算機(jī)是一種可確定孔轴，可預(yù)測(cè)的的設(shè)備剃法，沒(méi)法通過(guò)一行一行的確定的代碼本身自身產(chǎn)生真隨機(jī)，產(chǎn)生的所謂隨機(jī)數(shù)全部都是偽隨機(jī)路鹰，最多只能做到范圍足夠大贷洲，產(chǎn)生規(guī)律足夠復(fù)雜，感覺(jué)像是隨機(jī)而已晋柱。
7.參考文獻(xiàn)
參考二：?由亂序播放說(shuō)開(kāi)了去
參考三：?數(shù)組的完全隨機(jī)排列
8.更多討論
PPT：https://ptteng.github.io/PPT/PPT-java/Java-1-page.html#/
