shuffle算法，我把他叫做洗牌算法，它的目标正好与各种的sort算法相反，即把一个有序(或者无序)的一系列元素打乱，以满足需求。

举个两例子，大家都知道扑克牌，我们每次都需要在摸牌之前把牌洗掉，用来让每个人摸到每张牌的概率尽量相等，增加游戏的随机性和乐趣；还有音频播放器，有一些人不喜欢顺序播放，而喜欢使用随机播放(其实随机播放分为两种,random和shuffle，后文会介绍到)，比如iPod Shuffle的卖点之一就是“你永远不知道你将要听到的下一首歌曲是什么”。至少，如果要模拟扑克牌游戏，或者做音频播放器，都要使用shuffle算法，而二者的shuffle算法却有一些区别，一个是一次性的洗牌，另一个则是每次取一首歌。那么怎么实现他们呢？

扑克牌的shuffle算法：

下面为了方便和容易读懂，我都用扑克牌来作例子：桌上有n张牌，并且对桌子上的牌进行标号，从0直到n-1。我们的目的是洗这些牌。

一个比较容易想到的方法是，桌子上有n张扑克牌，我第i次从桌子上等概率随机取一张扑克牌，作为洗牌后牌堆的第i张扑克牌，那么这个算法实现起来应该是这样的：

伪代码：
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开始数)在剩下的n-i张牌里等概率的取一张牌，把它放到shuffle里。而deck[d] = deck[n - i]这句达到的效果是删除取过的牌。

这个方法的时间复杂度是O(n)，已经可以接受了，但这个方法还不够好，因为我们需要两个长度为n数组。其实可以很容易得得到下面的方法，解决空间的问题：
伪代码：
for i <- 0 to n - 1
do d <- Random mod (n - i)
   swap(deck[d], deck[n - i])

这样，这个算法的道理就有些像选择排序了，第i次(从0开始数)确定第n-i个元素的原位置，并且交换两个位置上的元素。它的复杂读仍然是O(n)，而只需要1个额外的空间来储存交换用的临时变量。
这个方法已经是一个比较好的解决方法了(自己认为)，如果你还能写出更好的shuffle算法，请告诉我。

我相信对洗牌这种东西有了解的人都不会用这样的方法来洗牌：另外对每张牌做一个标记，即是否抽过这张牌：然后第i次在n张牌里随机抽一个，如果这张牌曾经被抽过，那么把它放回去，重复抽取，直到抽到一张没被抽过的牌，将这张牌标记为抽取过的牌，然后在纸上的第i个地方记下这张牌。在计算机里这样实现：

伪代码：
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]


看了描述，你一定就会觉得这种方法实在是遭透了，不仅麻烦，而且会有一个陷阱，那就是在某次取牌的时候，也许会运气差永远也取不到没有被取过的那张牌，导致程序运行的不确定性。然而，在初学者当中，却有不少是用这种方法实现的shuffle的。个人认为，在设计算法的时候，越简单、越接近生活的模型，就越容易设计出好的算法，而且算法的描述也更接近实际生活。因此，设计算法的时候，如果能往平时生活的方面想， 总是事半功倍的。

附上我自己实现的一个类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算法：

前面说过播放器的随机播放有两种，一种叫Random,一种叫Shuffle(我自己理解的......)，下面解释这两种方法的不同。

学过概率的人都该知道有放回的抽取的概念。袋中有n个不同的小球，每次抽取一个小球，然后放回，每一次取的时候概率都是相同的。这正是播放器random算法的原理，这种算法实现起来很简单，一首歌结束以后，只需要随机选取下一首歌就行了。
但是这样做有一些缺点：1，有一定的概率使得连续选取的两首歌是同一首歌，我相信并不是所有人都希望在shuffle模式下连续听同一首歌吧，当然也有解决办法，那就是增加层循环判断，如果选上同一首歌，则重新选，而这样又会重蹈那个很烂的洗牌算法的覆辙。2，当听完一首歌的时候，觉得还想再听一遍，怎么办？按下“上一首”，你会发现这时听到的歌曲已经不是刚才那一首想听歌曲了，因为这种方法只知道当前的状态，而不知道过去的播放状态。怎么办？一种办法是增加一个队列叫做“刚才播放列表”，把播放过的歌曲按照顺序储存在列表里。3，有一定概率在很长的一段时间内，播放器不停的在重复播放两首歌曲A和B或者类似情况，就像这样：...-A-B-A-B-A-B-...。这种情况也是很讨厌的，可是如何避免呢？我能想到的办法是增加判断，看这首歌是不是在列表的最后几项里，如果在就不选这首......

但是这些概率都小的可怜，对于一个播放器的random函数来说，能够考虑到以上的几点，已经能够做到足够random和人性化了。只要能够合理的选择参数，考虑到一些特殊情况(比如极小的播放列表)，以及考虑用户的心理，就能做出一个比较好的random函数。

下面讲我设计的播放器shuffle算法，shuffle算法能够很大程度上避免random算法的缺陷，在空间时间上都很节约，而且能够达到比较理想的随机化效果。它的大体思路是这样的：

我们使用一个隐含的shuffle播放列表(一个循环队列)来储存歌曲的顺序，并用一个指针表示正在播放的歌曲(记作"^")，比如当前的播放列表是这样的：

ABCDEFGHIJKLMN
             ^

即现在有14首歌，将要播放位置1的歌曲(正在播放位置14的歌曲)，我们认为队列头和尾是相连的，即N后面的元素是A，那么这样够成了一个循环队列。
在播放之前，我们在前7(7=14*0.5，这个比例可以随便选，当然越大随机性越大，但能后退的次数越少)个位置中，随机取一个一首歌，把它和将要播放的那个位置的歌曲交换。假设我们选的是E，则队列变成这样：

EBCDAFGHIJKLMN
^

然后播放E。E播放完了以后(或者选择下一首时)，重复刚才的动作，即在BCDAFGH中随机选一个，交换，比如选到H，则队列变成：
EHCDAFGBIJKLMN
 ^

然后播放H。这样，一个shuffle算法初步完成了。

比如某一时刻播放器的状态是这样：
EHCDAFGBIJKLMN
          ^
则我们在LMNEHCD中选择一个，比如选择到H，那么交换并播放，成为：
ELCDAFGBIJKHMN
           ^
但是如果用户选择上一首怎么办呢?我们可以再记录一个指针指向最新shuffle选择出来的那首歌曲(记作"*")，没有选择过前一首的时候，它与播放指针指向同一个位置。当选择前一首的时候，仅移动指针^，而不移动*，比如上一个例子播放的时候按下前一首以后，成为：

ELCDAFGBIJKHMN
          ^*

这时候播放的K正好是刚才播放的那一首，当然这达到了我的目的，即可以选到刚才播放的曲目，当然如果再一次选择上一首，就会变成：

ELCDAFGBIJKHMN
         ^ *

这时候如果按下一首，应该判断^指向的是不是和*指向的相同，如果相同，就按照最早介绍的shuffle算法进行随机选取，不相同就简单的移动^，即成为：

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算法比较简单实用，而且节约内存开销(这对mp3 walkman之类的东西是十分重要的)，当然也有个小缺点，就是当^前移多次回到*以后，再按下一首，则会重新开始shuffle，但是歌曲数目很多的情况下，这个缺点并不是那么重要。
这个算法在刚开始听的时候，并不是很随机，可是随着听的次数的增多，队列会越来越乱，达到一个shuffle的效果。
当然，也可以在第一次对这个列表播放之前，使用扑克牌的shuffle算法(见本文第一部分)进行一次shuffle，这样，刚开始播放的时候列表就是随机的。
通过原理我们可以看到，对于刚听过的那首歌来说，不经过length / 2次，是不会再一次听到的，因此很大程度上避免了random算法的缺陷。这个length / 2的参数可以按照具体情况选择，可以是常数，也可以是随机数，也可以是和长度有关的一个数。