shuffle算法，我把他叫做洗牌算法，它的目標(biāo)正好與各種的sort算法相反，即把一個(gè)有序(或者無(wú)序)的一系列元素打亂，以滿足需求。

舉個(gè)兩例子，大家都知道撲克牌，我們每次都需要在摸牌之前把牌洗掉，用來(lái)讓每個(gè)人摸到每張牌的概率盡量相等，增加游戲的隨機(jī)性和樂(lè)趣；還有音頻播放器，有一些人不喜歡順序播放，而喜歡使用隨機(jī)播放(其實(shí)隨機(jī)播放分為兩種,random和shuffle，后文會(huì)介紹到)，比如iPod Shuffle的賣點(diǎn)之一就是“你永遠(yuǎn)不知道你將要聽(tīng)到的下一首歌曲是什么”。至少，如果要模擬撲克牌游戲，或者做音頻播放器，都要使用shuffle算法，而二者的shuffle算法卻有一些區(qū)別，一個(gè)是一次性的洗牌，另一個(gè)則是每次取一首歌。那么怎么實(shí)現(xiàn)他們呢？

撲克牌的shuffle算法：

下面為了方便和容易讀懂，我都用撲克牌來(lái)作例子：桌上有n張牌，并且對(duì)桌子上的牌進(jìn)行標(biāo)號(hào)，從0直到n-1。我們的目的是洗這些牌。

一個(gè)比較容易想到的方法是，桌子上有n張撲克牌，我第i次從桌子上等概率隨機(jī)取一張撲克牌，作為洗牌后牌堆的第i張撲克牌，那么這個(gè)算法實(shí)現(xiàn)起來(lái)應(yīng)該是這樣的：

偽代碼：
for i <- 0 to n - 1
do d <- Random mod (n - i)
   shuffle[i] <- deck[d]
   deck[d] <- deck[n - i]

其中，deck是洗牌前的序列(0~n-1)，shuffle是洗牌后的序列(0~n-1)，第i次(從0開(kāi)始數(shù))在剩下的n-i張牌里等概率的取一張牌，把它放到shuffle里。而deck[d] = deck[n - i]這句達(dá)到的效果是刪除取過(guò)的牌。

這個(gè)方法的時(shí)間復(fù)雜度是O(n)，已經(jīng)可以接受了，但這個(gè)方法還不夠好，因?yàn)槲覀冃枰獌蓚€(gè)長(zhǎng)度為n數(shù)組。其實(shí)可以很容易得得到下面的方法，解決空間的問(wèn)題：
偽代碼：
for i <- 0 to n - 1
do d <- Random mod (n - i)
   swap(deck[d], deck[n - i])

這樣，這個(gè)算法的道理就有些像選擇排序了，第i次(從0開(kāi)始數(shù))確定第n-i個(gè)元素的原位置，并且交換兩個(gè)位置上的元素。它的復(fù)雜讀仍然是O(n)，而只需要1個(gè)額外的空間來(lái)儲(chǔ)存交換用的臨時(shí)變量。
這個(gè)方法已經(jīng)是一個(gè)比較好的解決方法了(自己認(rèn)為)，如果你還能寫出更好的shuffle算法，請(qǐng)告訴我。

我相信對(duì)洗牌這種東西有了解的人都不會(huì)用這樣的方法來(lái)洗牌：另外對(duì)每張牌做一個(gè)標(biāo)記，即是否抽過(guò)這張牌：然后第i次在n張牌里隨機(jī)抽一個(gè)，如果這張牌曾經(jīng)被抽過(guò)，那么把它放回去，重復(fù)抽取，直到抽到一張沒(méi)被抽過(guò)的牌，將這張牌標(biāo)記為抽取過(guò)的牌，然后在紙上的第i個(gè)地方記下這張牌。在計(jì)算機(jī)里這樣實(shí)現(xiàn)：

偽代碼：
for i <- 0 to n - 1
do d <- Random mod n
   while did[d] = 1
   do d = Random mod n
   did[d] <- 1
   shuffle[i] <- deck[d]


看了描述，你一定就會(huì)覺(jué)得這種方法實(shí)在是遭透了，不僅麻煩，而且會(huì)有一個(gè)陷阱，那就是在某次取牌的時(shí)候，也許會(huì)運(yùn)氣差永遠(yuǎn)也取不到?jīng)]有被取過(guò)的那張牌，導(dǎo)致程序運(yùn)行的不確定性。然而，在初學(xué)者當(dāng)中，卻有不少是用這種方法實(shí)現(xiàn)的shuffle的。個(gè)人認(rèn)為，在設(shè)計(jì)算法的時(shí)候，越簡(jiǎn)單、越接近生活的模型，就越容易設(shè)計(jì)出好的算法，而且算法的描述也更接近實(shí)際生活。因此，設(shè)計(jì)算法的時(shí)候，如果能往平時(shí)生活的方面想， 總是事半功倍的。

附上我自己實(shí)現(xiàn)的一個(gè)類qsort的shuffle算法

// element_Size is the size of each element
 
void swap(void const *element1, void const *element2, size_t element_Size)
{
    char *temp = new char,
         *elem1, *elem2;
    elem1 = (char *)element1;
    elem2 = (char *)element2;
    for(int i = 0; i < element_Size; i++, elem1++, elem2++){
        *temp = *elem1;
        *elem1 = *elem2;
        *elem2 = *temp;
    }
    delete temp;
}
 
// array_Size is the size of array,
// element_Size is the size of each element in array
 
void shuffle(void const *array, size_t array_Size, size_t element_Size)
{
    void *element1, *element2;
    srand(time(0));
    for(int i = 0; i < array_Size / element_Size; i++){
        element1 = (char *)array + i * element_Size;
        element2 = (char *)array + rand(i * element_Size,
            array_Size - element_Size, element_Size);
        swap(element1, element2, element_Size);
    }
}

播放器的shuffle算法：

前面說(shuō)過(guò)播放器的隨機(jī)播放有兩種，一種叫Random,一種叫Shuffle(我自己理解的......)，下面解釋這兩種方法的不同。

學(xué)過(guò)概率的人都該知道有放回的抽取的概念。袋中有n個(gè)不同的小球，每次抽取一個(gè)小球，然后放回，每一次取的時(shí)候概率都是相同的。這正是播放器random算法的原理，這種算法實(shí)現(xiàn)起來(lái)很簡(jiǎn)單，一首歌結(jié)束以后，只需要隨機(jī)選取下一首歌就行了。
但是這樣做有一些缺點(diǎn)：1，有一定的概率使得連續(xù)選取的兩首歌是同一首歌，我相信并不是所有人都希望在shuffle模式下連續(xù)聽(tīng)同一首歌吧，當(dāng)然也有解決辦法，那就是增加層循環(huán)判斷，如果選上同一首歌，則重新選，而這樣又會(huì)重蹈那個(gè)很爛的洗牌算法的覆轍。2，當(dāng)聽(tīng)完一首歌的時(shí)候，覺(jué)得還想再聽(tīng)一遍，怎么辦？按下“上一首”，你會(huì)發(fā)現(xiàn)這時(shí)聽(tīng)到的歌曲已經(jīng)不是剛才那一首想聽(tīng)歌曲了，因?yàn)檫@種方法只知道當(dāng)前的狀態(tài)，而不知道過(guò)去的播放狀態(tài)。怎么辦？一種辦法是增加一個(gè)隊(duì)列叫做“剛才播放列表”，把播放過(guò)的歌曲按照順序儲(chǔ)存在列表里。3，有一定概率在很長(zhǎng)的一段時(shí)間內(nèi)，播放器不停的在重復(fù)播放兩首歌曲A和B或者類似情況，就像這樣：...-A-B-A-B-A-B-...。這種情況也是很討厭的，可是如何避免呢？我能想到的辦法是增加判斷，看這首歌是不是在列表的最后幾項(xiàng)里，如果在就不選這首......

但是這些概率都小的可憐，對(duì)于一個(gè)播放器的random函數(shù)來(lái)說(shuō)，能夠考慮到以上的幾點(diǎn)，已經(jīng)能夠做到足夠random和人性化了。只要能夠合理的選擇參數(shù)，考慮到一些特殊情況(比如極小的播放列表)，以及考慮用戶的心理，就能做出一個(gè)比較好的random函數(shù)。

下面講我設(shè)計(jì)的播放器shuffle算法，shuffle算法能夠很大程度上避免random算法的缺陷，在空間時(shí)間上都很節(jié)約，而且能夠達(dá)到比較理想的隨機(jī)化效果。它的大體思路是這樣的：

我們使用一個(gè)隱含的shuffle播放列表(一個(gè)循環(huán)隊(duì)列)來(lái)儲(chǔ)存歌曲的順序，并用一個(gè)指針表示正在播放的歌曲(記作"^")，比如當(dāng)前的播放列表是這樣的：

ABCDEFGHIJKLMN
             ^

即現(xiàn)在有14首歌，將要播放位置1的歌曲(正在播放位置14的歌曲)，我們認(rèn)為隊(duì)列頭和尾是相連的，即N后面的元素是A，那么這樣夠成了一個(gè)循環(huán)隊(duì)列。
在播放之前，我們?cè)谇?(7=14*0.5，這個(gè)比例可以隨便選，當(dāng)然越大隨機(jī)性越大，但能后退的次數(shù)越少)個(gè)位置中，隨機(jī)取一個(gè)一首歌，把它和將要播放的那個(gè)位置的歌曲交換。假設(shè)我們選的是E，則隊(duì)列變成這樣：

EBCDAFGHIJKLMN
^

然后播放E。E播放完了以后(或者選擇下一首時(shí))，重復(fù)剛才的動(dòng)作，即在BCDAFGH中隨機(jī)選一個(gè)，交換，比如選到H，則隊(duì)列變成：
EHCDAFGBIJKLMN
 ^

然后播放H。這樣，一個(gè)shuffle算法初步完成了。

比如某一時(shí)刻播放器的狀態(tài)是這樣：
EHCDAFGBIJKLMN
          ^
則我們?cè)贚MNEHCD中選擇一個(gè)，比如選擇到H，那么交換并播放，成為：
ELCDAFGBIJKHMN
           ^
但是如果用戶選擇上一首怎么辦呢?我們可以再記錄一個(gè)指針指向最新shuffle選擇出來(lái)的那首歌曲(記作"*")，沒(méi)有選擇過(guò)前一首的時(shí)候，它與播放指針指向同一個(gè)位置。當(dāng)選擇前一首的時(shí)候，僅移動(dòng)指針^，而不移動(dòng)*，比如上一個(gè)例子播放的時(shí)候按下前一首以后，成為：

ELCDAFGBIJKHMN
          ^*

這時(shí)候播放的K正好是剛才播放的那一首，當(dāng)然這達(dá)到了我的目的，即可以選到剛才播放的曲目，當(dāng)然如果再一次選擇上一首，就會(huì)變成：

ELCDAFGBIJKHMN
         ^ *

這時(shí)候如果按下一首，應(yīng)該判斷^指向的是不是和*指向的相同，如果相同，就按照最早介紹的shuffle算法進(jìn)行隨機(jī)選取，不相同就簡(jiǎn)單的移動(dòng)^，即成為：

ELCDAFGBIJKHMN
          ^*

偽代碼：
function keypress(key)
   if key = NEXT
      if p1 = p2
      do p1 <- p1 + 1
         p2 <- p2 + 1
         k = Random mod (length / 2)
         swap(p1, (p1 + k) mod length)
         play(p2)
      else
      do p2 <- (p2 + 1) mod length
         play(p2)
   if key = PREV
      do p2 <- (p2 + length - 1) mod length
         play(p2)

這個(gè)播放器的shuffle算法比較簡(jiǎn)單實(shí)用，而且節(jié)約內(nèi)存開(kāi)銷(這對(duì)mp3 walkman之類的東西是十分重要的)，當(dāng)然也有個(gè)小缺點(diǎn)，就是當(dāng)^前移多次回到*以后，再按下一首，則會(huì)重新開(kāi)始shuffle，但是歌曲數(shù)目很多的情況下，這個(gè)缺點(diǎn)并不是那么重要。
這個(gè)算法在剛開(kāi)始聽(tīng)的時(shí)候，并不是很隨機(jī)，可是隨著聽(tīng)的次數(shù)的增多，隊(duì)列會(huì)越來(lái)越亂，達(dá)到一個(gè)shuffle的效果。
當(dāng)然，也可以在第一次對(duì)這個(gè)列表播放之前，使用撲克牌的shuffle算法(見(jiàn)本文第一部分)進(jìn)行一次shuffle，這樣，剛開(kāi)始播放的時(shí)候列表就是隨機(jī)的。
通過(guò)原理我們可以看到，對(duì)于剛聽(tīng)過(guò)的那首歌來(lái)說(shuō)，不經(jīng)過(guò)length / 2次，是不會(huì)再一次聽(tīng)到的，因此很大程度上避免了random算法的缺陷。這個(gè)length / 2的參數(shù)可以按照具體情況選擇，可以是常數(shù)，也可以是隨機(jī)數(shù)，也可以是和長(zhǎng)度有關(guān)的一個(gè)數(shù)。