之前用HTML5的Audio API寫了個音樂頻譜效果，再之后又加了個播放列表就成了個簡單的播放器，其中弄了個功能是'Shuffle'也就是一般播放器都有的列表打亂功能，或者理解為隨機播放。
但我覺得隨機播放絕對要好實現些，用Math.random()產生一個介于1到歌曲數目之間的隨機數便可，然后player.play(隨機數)。
而列表的打亂情況要不一樣點，一是要呈現到界面，歌曲順序要隨機排，二是播放順序不變，該哪是哪，只是該位置上的歌曲可能已經變成其他曲目了。抽象出來就是數組元素的重排，那么具體算法就值得探究了。
面對一個新問題時，我首先想到的是前人是否已經給出了問題的答案。正如所料于是發現了這個成熟的Fisher-Yates亂序算法，這是公認經典的洗牌算法了。但事情到此并沒有結束。
原文給出了三個循序漸近的例子，下面來看。
一般化方法
原文引入的現實情境是這樣的，假如你要洗牌，那么最隨機的做法無疑是從牌堆里隨便抽一張出來，然后放在一邊，之后從剩下的牌里重復之前的操作，直到所有牌都被抽出來放到了另一堆中。抽象到代碼世界，按相同的做法，就是隨機從數組里取出一個元素，保存到另一個數組，然后重復之，直到原數組中所有元素都處理掉。
原文給出的演示我覺得不夠直觀，下方是我自己寫的動畫用以演示此算法過程（也可在這里查看：http://sandbox.runjs.cn/show/1hylhpck ）：
下面是按這個思路的一個實現:
function shuffle(array) {
var copy = [],
n = array.length,
i;
// 如果還剩有元素則繼續。。。
while (n) {
// 隨機抽取一個元素
i = Math.floor(Math.random() * array.length);
// 如果這個元素之前沒有被選中過。。
if (i in array) {
copy.push(array[i]);
delete array[i];
n--;
}
}
return copy;
}
我們創建了一個copy數組，然后遍歷目標數組，將其元素復制到copy數組里，同時將該元素從目標數組中刪除，這樣下次遍歷的時候就可以跳過這個序號。而這一實現的問題正在于此，即使一個序號上的元素已經被處理過了，由于隨機函數產生的數是隨機的，所有這個被處理過的元素序號可能在之后的循環中不斷出現，一是效率問題，另一個就是邏輯問題了，存在一種可能是永遠運行不完！
Note:
Math.random()產生[0,1)的小數
delete 操作只將數組元素的值刪除，但不影響數組長度，刪除后原來位置的值變為undefined
改進的做法
上面的分析已經看出問題的所在了，所以改進的做法就是處理完一個元素后，我們用Array的splice()方法將其從目標數組中移除同時也更新了目標數組的長度，如此一來下次遍歷的時候是從新的長度開始，不會重復處理的情況了。
動畫演示（http://sandbox.runjs.cn/show/v6a7gq0f）
function shuffle(array) {
var copy = [],
n = array.length,
i;
// 如果還剩有元素。。
while (n) {
// 隨機選取一個元素
i = Math.floor(Math.random() * n--);
// 移動到新數組中
copy.push(array.splice(i, 1)[0]);
}
return copy;
}
再次優化的最終版本
上面的做法已經可以了，但上面的改進依然還有提升空間。因為調用splice來刪除數組元素會導致刪除位置之后的所有元素要做shift操作來向前補充，從而達到將數組長度減小的目的，當然這是在后臺自動完成的，但這無疑增加了算法的復雜度。
注意到我們要做的僅僅是將數組元素重新排序，已經取出來的元素和剩下的元素之和一定是等于數組原來的總元素個數的。所以可以考慮不創建新的數組來保存已經抽取的元素，可以這樣，隨機從數組中抽出一個元素，然后與最后個元素交換，相當于把這個隨機抽取的元素放到了數組最后面去，表示它已經是被隨機過了，同時被換走的那個元素跑到前面去了，會在后續的重復操作中被隨機掉。一輪操作過后，下一輪我們只在剩下的n-1個元素也就是數組的前n-1個元素中進行相同的操作，直到進行到第一個。
動畫演示（http://sandbox.runjs.cn/show/jabgttzr）：
function shuffle(array) {
var m = array.length,
t, i;
// 如果還剩有元素…
while (m) {
// 隨機選取一個元素…
i = Math.floor(Math.random() * m--);
// 與當前元素進行交換
t = array[m];
array[m] = array[i];
array[i] = t;
}
return array;
}
更加簡潔的版本
上面介紹的便是在各語言中都廣為實現的Fisher-Yates亂序算法。但具體到JavaScript，我們其實可以結合數組自帶的sort()方法編寫出更簡潔的代碼來達到目的。中間變量以及值交換什么的都省了，雖然后臺實現肯定還是會進行值交換的，但我們不關心，一切交給sort()讓它自己處理。但這種方法也只是簡潔而以，效果是不如上面介紹的算法的，因為隨著數組元素越多，其隨機性會變差。
function shuffle(array) {
return array.sort(function() {
return Math.random() - 0.5
});
}
REFERENCE
- Fisher–Yates Shuffle: http://bost.ocks.org/mike/shuffle/
- Why the Fisher-Yates Shuffle is the best algorithm from Quora: http://www.quora.com/Algorithms/Are-there-any-better-shuffling-algorithms-than-Fisher%E2%80%93Yates-shuffle
- 45 Useful JavaScript Tips, Tricks and Best Practices http://flippinawesome.org/2013/12/23/45-useful-javascript-tips-tricks-and-best-practices/
文章列表
留言列表
