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; } } 

Answer 1

首先，您应该提取用于生成一个随机数的代码，该随机数在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函数的所有n的rand_int必须是n! 。