学步园

偶尔看到有人在讨论如何生成不重复的随机数系列（洗牌算法），发现他们用的方法复杂度十分高，要抛大量的随机数，因此把我以前用的洗牌算法也拿出来秀秀。

假设需要生成 1~54 的随机数，那么把 1~54 放入“未洗牌数组”，抛 0~53 的随机数，把指定序号的牌，放入“洗好牌的数组"，然后用未洗牌数组中最后一张牌替换已经被拿走的牌。

下一步，抛 0~52 的随机数……

重复 53 次就可以洗完牌，只需要53个随机数，53次赋值，复杂度相当低，可以在常数时间内完成。

演示代码如下：

int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> srand( (unsigned int)time(NULL) );<br /> std::vector<int> ramdon_cards; // 存放结果<br /> const int count=54;<br /> int cards[count];<br /> // 初始化未洗牌数组<br /> for( int i=0; i<count; ++i )<br /> cards[i]=i+1;<br /> for( int i=count; i>0; --i ){<br /> int index=rand() % i;<br /> ramdon_cards.push_back( cards[index] ); // 随机拿走容器中的一张牌<br /> cards[index]=cards[i-1]; // 用最后一张牌替换被拿走的牌<br /> }<br /> std::copy(ramdon_cards.begin(), ramdon_cards.end(), std::ostream_iterator<int>(std::cout, " "));<br /> return 0;<br /> }<br />  

PS: 其实如果使用 C++ 的话，STL 的算法库里直接有一个算法函数叫 random_shuffle() 就可以完成这个工作。