正确的算法

　　下面，我们来看看性能高且正确的算法—— 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