正确的算法
下面，我们来看看性能高且正确的算法—— Fisher_Yates 算法
void ShuffleArray_Fisher_Yates (char* arr, int len)
{
int i = len, j;
char temp;
if ( i == 0 ) return;
while ( --i ) {
j = rand () % (i+1);
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} |
这个算法不难理解，看看测试效果（效果明显比前面的要好）：
1 2 3 4 5 6 7 8 9 10
-----------------------------------------------------
A | 107 98 83 115 89 103 105 99 94 107
B | 91 106 90 102 88 100 102 97 112 112
C | 100 107 99 108 101 99 86 99 101 100
D | 96 85 108 101 117 103 102 96 108 84
E | 106 89 102 86 88 107 114 109 100 99
F | 109 96 87 94 98 102 109 101 92 102
G | 94 95 119 110 97 112 89 101 89 94
H | 93 102 102 103 100 89 107 105 101 98
I | 99 110 111 101 102 79 103 89 104 102
J | 105 112 99 99 108 106 95 95 99 82 |
但是我们可以看到还是不完美。因为我们使用的 rand ()是伪随机数，不过已经很不错的。最大的误差在 20% 左右。
我们再来看看洗牌 100 万次的统计值，你会看到误差在6% 以内了。这个对于伪随机数生成的程序已经很不错了。
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------------------------
A | 100095 99939 100451 99647 99321 100189 100284 99565 100525 99984
B | 99659 100394 99699 100436 99989 100401 99502 100125 100082 99713
C | 99938 99978 100384 100413 100045 99866 99945 100025 99388 100018
D | 99972 99954 99751 100112 100503 99461 99932 99881 100223 100211
E | 100041 100086 99966 99441 100401 99958 99997 100159 99884 100067
F | 100491 100294 100164 100321 99902 99819 99449 100130 99623 99807
G | 99822 99636 99924 100172 99738 100567 100427 99871 100125 99718
H | 99445 100328 99720 99922 100075 99804 100127 99851 100526 100202
I | 100269 100001 99542 99835 100070 99894 100229 100181 99718 100261
J | 100268 99390 100399 99701 99956 100041 100108 100212 99906 100019 |
如何写测试案例
测试程序其实很容易写了。就是，设置一个样本大小，做一下统计，然后计算一下误差值是否在可以容忍的范围内。比如：
● 样本：100万次
● 最大误差：10% 以内
● 平均误差：5% 以内 （或者：90% 以上的误差要小于5%）
本文出自：http://coolshell.cn/articles/8593.html
