以下是Fisher-Yates的C实现,我想使用一个甲板洗牌程序.我正在做这个(n =数组的长度)？
注意：do-while循环尝试纠正模偏(见here).它为该过程增加了一些开销,如果不关心低位偏差,可以消除该过程.
- void shuffle(int *array,int n) {
- int i,j,tmp,upper_bound;
- srand(time(NULL));
- for (i = n - 1; i > 0; i--) {
- upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1);
- do {
- j = rand() % (i + 1);
- } while (j > upper_bound);
- tmp = array[j];
- array[j] = array[i];
- array[i] = tmp;
- }
- }
解决方法
首先,您应该提取用于生成在0(包括)和n(独占)之间均等分配到一个单独的函数的随机数的代码.这也是您在其他地方需要工作的一项不错的工作.
第二,我不会在洗牌功能中调用srand,而是依赖于调用者初始化随机数生成器.这样你可以在一秒钟内洗牌一次以上.
第三,你应该做j>的测试. upper_bound除以i 1.我不大可能会接近RAND_MAX.
- static int rand_int(int n) {
- int limit = RAND_MAX - RAND_MAX % n;
- int rnd;
- do {
- rnd = rand();
- } while (rnd >= limit);
- return rnd % n;
- }
- void shuffle(int *array,int n) {
- int i,tmp;
- for (i = n - 1; i > 0; i--) {
- j = rand_int(i + 1);
- tmp = array[j];
- array[j] = array[i];
- array[i] = tmp;
- }
- }
要检查此实现是否正确,您需要确保随机数生成器询问log2(n！)位的随机性.换句话说,给予rand_int函数的所有ns的乘积必须是n！
