大多数人的实现
下面这个算法是大多数人的实现，就是 for 循环一次，然后随机交换两个数
void ShuffleArray_General (char* arr, int len)
{
const int suff_time = len;
for(int idx=0; idx int i = rand () % len;
int j = rand () % len;
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} |
跑起来也还不错，洗得挺好的。
第一次：G F C D A J B I H E
第二次：D G J F E I A H C B
第三次：C J E F A D G B H I
第四次：H D C F A E B J I G
第五次：E A J F B I H G D C |
但是上述三个算法哪个的效果更好？好像都是对的。一般的 QA 或是程序员很有可能就这样把这个功能 Pass 了。但是事情并没有那么简单……
如何测试
在做测试之前，我们还需要了解一下一个基本知识——PC 机上是做不出真随机数的，只能做出伪随机数。真随机数需要硬件支持。但是不是这样我们就无法测试了呢，不是的。我们依然可以测试。
我们知道，洗牌洗得好不好，主要是看是不是够随机。那么如何测试随机性呢？
试想，我们有个随机函数 rand ()返回 1 到 10 中的一个数，如果够随机的话，每个数返回的概率都应该是一样的，也就是说每个数都应该有 10 分之 1 的概率会被返回。
一到概率问题，我们只有一个方法来做测试，那就是用统计的方式。也就是说，你调用 rand ()函数 100 次，其中，每个数出现的次数大约都在 10 次左右。（注意：我用了左右，这说明概率并不是很准确的）不应该有一个数出现了 15 次以上，另一个在 5 次以下，要是这样的话，这个函数就是错的。
举一反三，测试洗牌程序也一样，需要通过概率的方式来做统计，是不是每张牌出现在第一个位置的次数都是差不多的。
于是，这样一来上面的程序就可以很容易做测试了。
下面是测试结果（测试样本 1000 次——列是每个位置出现的次数，行是各个字符的统计，出现概率应该是1/10，也就是 100 次）：
递归取中法
很明显，这个洗牌程序太有问题。算法是错的！
1 2 3 4 5 6 7 8 9 10
----------------------------------------------------
A | 101 283 317 208 65 23 3 0 0 0
B | 101 191 273 239 127 54 12 2 1 0
C | 103 167 141 204 229 115 32 7 2 0
D | 103 103 87 128 242 195 112 26 3 1
E | 104 83 62 67 116 222 228 93 22 3
F | 91 58 34 60 69 141 234 241 65 7
G | 93 43 35 19 44 102 174 274 185 31
H | 94 28 27 27 46 68 94 173 310 133
I | 119 27 11 30 28 49 64 96 262 314
J | 91 17 13 18 34 31 47 88 150 511 |
快排 Hack 法
看看对角线（从左上到右下）上的数据，很离谱！所以，这个算法也是错的。
1 2 3 4 5 6 7 8 9 10
-----------------------------------------------------
A | 74 108 123 102 93 198 40 37 52 173
B | 261 170 114 70 49 28 37 76 116 79
C | 112 164 168 117 71 37 62 96 116 57
D | 93 91 119 221 103 66 91 98 78 40
E | 62 60 82 90 290 112 95 98 71 40
F | 46 60 63 76 81 318 56 42 70 188
G | 72 57 68 77 83 39 400 105 55 44
H | 99 79 70 73 87 34 124 317 78 39
I | 127 112 102 90 81 24 57 83 248 76
J | 54 99 91 84 62 144 38 48 116 264 |
大多数人的算法
我们再来看看大多数人的算法。还是对角线上的数据有问题，所以，还是错的。
1 2 3 4 5 6 7 8 9 10
-----------------------------------------------------
A | 178 98 92 82 101 85 79 105 87 93
B | 88 205 90 94 77 84 93 86 106 77
C | 93 99 185 96 83 87 98 88 82 89
D | 105 85 89 190 92 94 105 73 80 87
E | 97 74 85 88 204 91 80 90 100 91
F | 85 84 90 91 96 178 90 91 105 90
G | 81 84 84 104 102 105 197 75 79 89
H | 84 99 107 86 82 78 92 205 79 88
I | 102 72 88 94 87 103 94 92 187 81
J | 87 100 90 75 76 95 72 95 95 215 |
