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

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

撲克牌的shuffle算法：

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

一個比較容易想到的方法是，桌子上有n張撲克牌，我第i次從桌子上等概率隨機(jī)取一張撲克牌，作為洗牌后牌堆的第i張撲克牌，那么這個算法實現(xiàn)起來應(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開始數(shù))在剩下的n-i張牌里等概率的取一張牌，把它放到shuffle里。而deck[d] = deck[n - i]這句達(dá)到的效果是刪除取過的牌。

這個方法的時間復(fù)雜度是O(n)，已經(jīng)可以接受了，但這個方法還不夠好，因為我們需要兩個長度為n數(shù)組。其實可以很容易得得到下面的方法，解決空間的問題：
偽代碼：
for i <- 0 to n - 1
do d <- Random mod (n - i)
   swap(deck[d], deck[n - i])

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

我相信對洗牌這種東西有了解的人都不會用這樣的方法來洗牌：另外對每張牌做一個標(biāo)記，即是否抽過這張牌：然后第i次在n張牌里隨機(jī)抽一個，如果這張牌曾經(jīng)被抽過，那么把它放回去，重復(fù)抽取，直到抽到一張沒被抽過的牌，將這張牌標(biāo)記為抽取過的牌，然后在紙上的第i個地方記下這張牌。在計算機(jī)里這樣實現(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]


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

附上我自己實現(xiàn)的一個類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算法：

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

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

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

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

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

ABCDEFGHIJKLMN
             ^

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

EBCDAFGHIJKLMN
^

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

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

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

ELCDAFGBIJKHMN
          ^*

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

ELCDAFGBIJKHMN
         ^ *

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

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)

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