随机洗牌算法

先看看肖舸老师的文章：《随机洗牌算法复杂度的比较实例》http://tonyxiaohome.blog.51cto.com/blog/925273/313362

其实我最初想到的也是那3个方法：1判断生成的随机数有没有重复，2.生成一张布尔表，3.双随机数。

下面给出我的算法：

#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
void RandCard(vector<int>, int);    //函数声明

int main(int argc, char *argv[])
{
	vector<int> nRetCard;
	int nCards=54;
	RandCard(nRetCard, nCards);
	return 0;
}

void RandCard(vector<int> nRetCard, int nCards)
{
	int i, j, temp;
	for(i=0; i<nCards; i++)
	{
		nRetCard.push_back(i+1);    //顺序生成初始值
	}
	srand(time(NULL));
	for(i=0, j=nCards; i<nCards; i++, j--)    //算法时间复杂度为O(n)
	{
		temp=rand()%j;    //从向量中随机取一个
		cout<<nRetCard[temp]<<" ";
		if( !((i+1)%17) ) cout<<endl;    //每隔17个换行
		nRetCard.erase(nRetCard.begin()+temp);    //删除用过的元素
	}
}

其思路很简单，每次从向量中随机取一个数出来，利用vevtor向量的自动调整长度，每次删除一个元素，再用新的向量长度j生成随机数：temp=rand()%j; 显然算法的时间复杂度为O(n)，即一趟for循环，不存在最坏情况。

 

如果是PHP语言，那么它自带了一个随机洗牌的函数，即shuffle()，它的作用是随机地对数组元素重新排序。其形式为：

void shuffle(array input_array)

考虑一个数组，其中包含扑克牌的值：

$cards = array("jh","js","jd","jc","qh","qs","qd","qc","kh","ks","kd","kc","ah","as","ad","ac");

$positions=shuffle($cards);

print_r($positions);    //输出随机排序后的结果

另外PHP中的array_rand()函数可从数组中随机出一个或多个键，其形式为：

mixed array_rand(array array [, int num_entries] )

如果忽略可选的num_entries参数，则只返回一个随机值。可以通过设置num_entries来调整返回随机值的个数。