本文共 6645 字，大约阅读时间需要 22 分钟。
我希望本文有助于你了解测试软件是一件很重要也是一件不简单的事。
我们有一个程序，叫ShuffleArray()，是用来洗牌的，我见过N多千变万化的ShuffleArray()，但是似乎从来没有要想过怎么去测试之。所以，我在面试中我经常会问如何测试ShuffleArray()，没想到这个问题居然难倒了很多有多年编程经验的人。对于这类的问题，其实，测试程序可能比算法更难写，代码更多。而这个问题正好可以加强一下我在《》中我所推崇的——开发人员更适合做测试的观点。
我们先来看几个算法（第一个比较诡异高深，第二个比较偷机取巧，第三个比较通俗易懂）
有一次是有一个朋友做了一个网页版的扑克游戏，他用到的算法比较诡异，是用递归+二分法，我说这个程序恐怕不对吧。他觉得挺对的，说测试了没有问题。他的程序大致如下（原来的是用Javascript写的，我在这里凭记忆用C复现一下）：
//递归二分方法const size_t MAXLEN = 10;const char TestArr[MAXLEN] = {'A','B','C','D','E','F','G','H','I','J'};static char RecurArr[MAXLEN]={0};static int cnt = 0;void ShuffleArray_Recursive_Tmp(char* arr, int len){ if(cnt > MAXLEN || len <=0){ return; } int pos = rand() % len; RecurArr[cnt++] = arr[pos]; if (len==1) return; ShuffleArray_Recursive_Tmp(arr, pos); ShuffleArray_Recursive_Tmp(arr+pos+1, len-pos-1);}void ShuffleArray_Recursive(char* arr, int len){ memset(RecurArr, 0, sizeof(RecurArr)); cnt=0; ShuffleArray_Recursive_Tmp(arr, len); memcpy(arr, RecurArr, len);}void main(){ char temp[MAXLEN]={0}; for(int i=0; i { strncpy(temp, TestArr, MAXLEN); ShuffleArray_Recursive((char*)temp, MAXLEN); }}
随便测试几次，还真像那么回事：
第一次：D C A B H E G F I J第二次：C A B D H G E F J I第三次：A B H F C E D G I J第四次：B A H G E C D F J I第五次：F B A D C E H G I J
让我们再看一个hack 快排的洗牌程序（只看算法，省去别的代码）：
int compare( const void *a, const void *b ){ return rand()%3-1;}void ShuffleArray_Sort(char* arr, int len){ qsort( (void *)arr, (size_t)len, sizeof(char), compare );} 运行个几次，感觉得还像那么回事：
第一次：H C D J F E A G B I第二次：B F J D C E I H G A第三次：C G D E J F B I A H第四次：H C B J D F G E I A第五次：D B C F E A I H G J
看不出有什么破绽。
下面这个算法是大多数人的实现，就是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 0B | 101 191 273 239 127 54 12 2 1 0C | 103 167 141 204 229 115 32 7 2 0D | 103 103 87 128 242 195 112 26 3 1E | 104 83 62 67 116 222 228 93 22 3F | 91 58 34 60 69 141 234 241 65 7G | 93 43 35 19 44 102 174 274 185 31H | 94 28 27 27 46 68 94 173 310 133I | 119 27 11 30 28 49 64 96 262 314J | 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 173B | 261 170 114 70 49 28 37 76 116 79C | 112 164 168 117 71 37 62 96 116 57D | 93 91 119 221 103 66 91 98 78 40E | 62 60 82 90 290 112 95 98 71 40F | 46 60 63 76 81 318 56 42 70 188G | 72 57 68 77 83 39 400 105 55 44H | 99 79 70 73 87 34 124 317 78 39I | 127 112 102 90 81 24 57 83 248 76J | 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 93B | 88 205 90 94 77 84 93 86 106 77C | 93 99 185 96 83 87 98 88 82 89D | 105 85 89 190 92 94 105 73 80 87E | 97 74 85 88 204 91 80 90 100 91F | 85 84 90 91 96 178 90 91 105 90G | 81 84 84 104 102 105 197 75 79 89H | 84 99 107 86 82 78 92 205 79 88I | 102 72 88 94 87 103 94 92 187 81J | 87 100 90 75 76 95 72 95 95 215
下面，我们来看看性能高且正确的算法——
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 107B | 91 106 90 102 88 100 102 97 112 112C | 100 107 99 108 101 99 86 99 101 100D | 96 85 108 101 117 103 102 96 108 84E | 106 89 102 86 88 107 114 109 100 99F | 109 96 87 94 98 102 109 101 92 102G | 94 95 119 110 97 112 89 101 89 94H | 93 102 102 103 100 89 107 105 101 98I | 99 110 111 101 102 79 103 89 104 102J | 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 99984B | 99659 100394 99699 100436 99989 100401 99502 100125 100082 99713C | 99938 99978 100384 100413 100045 99866 99945 100025 99388 100018D | 99972 99954 99751 100112 100503 99461 99932 99881 100223 100211E | 100041 100086 99966 99441 100401 99958 99997 100159 99884 100067F | 100491 100294 100164 100321 99902 99819 99449 100130 99623 99807G | 99822 99636 99924 100172 99738 100567 100427 99871 100125 99718H | 99445 100328 99720 99922 100075 99804 100127 99851 100526 100202I | 100269 100001 99542 99835 100070 99894 100229 100181 99718 100261J | 100268 99390 100399 99701 99956 100041 100108 100212 99906 100019
测试程序其实很容易写了。就是，设置一个样本大小，做一下统计，然后计算一下误差值是否在可以容忍的范围内。比如：
转载地址：http://vsosi.baihongyu.com/