比如，我们写一个生成包含 1 - 52 这些数字的数组，要求位置是打乱的，并且不允许有数字没出现，或者有数字重复出现
为了达到这个目标，典型的洗牌算法是，先生成一个 1 - 52 有序的数组，然后，做若干次交换操作，这样打乱效率较高，并且不会有数字重复的问题

于是，有人会写如下类似的代码（以下请看成伪代码）：

#define SWAP(a, b, _t) do{_t t = a; a = b; b = t; }while(0)

void shuffle(int* arr, int len)
{
    int n;
    for (n = 0; n < len; ++n)
    {
        int i = myrand(len); //生成一个 0 至 len-1之间的随机数，也可能写成 rand() % len
        SWAP(arr[n], arr[i], int); //交换arr[n]和arr[i]
    }
}

运行时，看起来效果也不错，这也是最为常见的写法，
即每次生成一个 0 至 len-1之间的随机数i，和原数组里依次每个数交换，保证每个数都交换了至少一次













如此广为流传的写法，殊不知，却是错的！尽管应用时看起来似乎没有什么问题




以下是算法分析：
在这里，一共做了len次交换，每一次随机范围大小都是len，那么一共产生的可能总数是pow(n,n)，即n的n次方

不过，len个数的全排列，是n!次，而pow(n,n)远比n!要大
而素数定理里，任意的n与2n之间至少存在一个素数，那么同理，n与n/2之间至少存在一个素数，并且这个素数是不能整除n的
所以，n!至少含有一个质因数，是pow(n, n)所不包含的，所以pow(n, n)绝不可能是n!的整数倍
所以，pow(n, n)所产生的组合，概率一定是不完全均等的，有一些排列出现概率高，有一些概率低，
所以，这种办法生成的排列，概率是不均匀分布的

为了更直观地说明问题，我用三个数1,2,3的排列，用此算法打乱，看看各种排列出现的次数：

随机值   最后结果排列（字母表示排列类型）
0 0 0    3 1 2 e
0 0 1    2 3 1 d
0 0 2    2 1 3 c
0 1 0    3 2 1 f
0 1 1    1 3 2 b
0 1 2    1 2 3 a
0 2 0    2 3 1 d
0 2 1    1 2 3 a
0 2 2    1 3 2 b
1 0 0    3 2 1 f
1 0 1    1 3 2 b
1 0 2    1 2 3 a
1 1 0    3 1 2 e
1 1 1    2 3 1 d
1 1 2    2 1 3 c
1 2 0    1 3 2 b
1 2 1    2 1 3 c
1 2 2    2 3 1 d
2 0 0    1 3 2 b
2 0 1    2 1 3 c
2 0 2    2 3 1 d
2 1 0    1 2 3 a
2 1 1    3 1 2 e
2 1 2    3 2 1 f
2 2 0    2 1 3 c
2 2 1    3 2 1 f
2 2 2    3 1 2 e

统计一下：
1 2 3 : 4
1 3 2 : 5
2 1 3 : 5
2 3 1 : 5
3 1 2 : 4
3 2 1 : 4

总排列数是6，而27种生成结果是无论如何也不可能平均下去的
其中，随机值是指myrand(len)的返回值，每次生成调用了三次，就有三个值
数据中，清晰可见，每种排列出现次数并不一样，而且，如果长度不止3，那么这种情况会更为严重，
次数差别会更大，更不均匀


在证明了这个算法是不对的以后，那正确的应该怎么写呢？
并不复杂，记住以下的代码吧：
#define SWAP(a, b, _t) do{_t t = a; a = b; b = t; }while(0)
void shuffle(int* arr, int len)
{
    int n;
    for (n = len; n > 1; --n)
    {
        int i = myrand(n);
        SWAP(arr[n - 1], arr[i], int);
    }
}

完.

收到的鲜花

• yangfanconan 于 2011-01-15 17:56 送鲜花  10朵   附言：好文章

你这样写是对的，这种做法就是我在最后给出的代码的做法

void shuffle(int* arr, int len)
{
    int n;
    for (n = 0; n < len; ++n)
    {
        int i = myrand(n);
        SWAP(arr[n], arr[i + n], int);
    }
}

这样也对，换个方向的写法

这种写法只是我个人的喜好，你写成其它的形式也是可以的，这也不是从什么书里找的