Fisher-Yates洗牌的C实现是否正确?

这是一个我想在甲板洗牌程序中使用的Fisher-Yates的C实现。 我正确地做这个(n =数组的长度)?

注意:do-while循环尝试纠正模偏移(参见这里 )。 它为程序增加了一些开销,如果你不关心低位偏差,可以将其消除。

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 (不含)之间平均分配给一个单独的函数。 这是你在别处也需要的一项很好的工作。

其次,我不会在shuffle函数中调用srand ,而是依赖调用者初始化随机数生成器。 这样,你可以在一秒钟内多次洗牌。

第三,在除以i + 1之前,你应该对j > upper_bound进行testing。 我不太可能会在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, j, 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函数的所有nrand_int必须是n!