最近一直搞数据库，很久没摸C语言，都快忘了。为了练手，前段时间一个没有完成的产生不重复随机序列的算法重写一遍。
C语言没有随机种子值的概念，所以产生一个随机、不重复序列还不太容易。最常归的思路是：给定一个范围，然后做rand() %MAX_VALUE运算，如果发现该值已经取过，则重新产生一个值。这个算法，你会发现随着，当MAX_VALUE值大到一定程度时（我的测试值为20），就会陷入死循环。原因是，比如20个数，取了前面18个数，产生后面两个数的几率就会指数及减小，可能做上百万次运算，也无法产生最后两个数。于是自己重新想了一种算法。
算法原理：给出两个数列，产生一个随机数，将第二个数列该位置上的数，复制到第一个数列，然后对第二个数列进行压缩，知道所有的值都使用完为止。如图：
第一轮迭代
将临时数列进行压缩，进行第二轮迭代：
这样，基本可以产生一个均匀不重复的随机数列。但是，根据测试结果，同一个MAX_VALUE值，每次产生的随机数列是一样的，所以，若将此应用于生产，还需做其他处理。
源代码如下：
#include"stdafx.h"
#include
#include
#include
intrand_array(int* arr, int floor);
voidMergArr(int* pArr, int nSize);
#defineMAX_VALUE 10
int main(intargc, char** argv)
{
int rand_list[MAX_VALUE];
int ret = 0;
int i = 0;
ret = rand_array(rand_list, MAX_VALUE);
for (i = 0; i < MAX_VALUE; i++)
{
printf("rand_list[%d]:%d\r\n", i, rand_list[i]);
}
return 0;
}
intrand_array(int* pArrList, int nFloor)
{
int i = 0;
int* pArrTmp = NULL; // 临时数组
int nRand = 0;
int nTotal = 0;
int nLastSize = 0;
int nMemSize = nFloor * sizeof(int) +1;
// 先为数组分配内存
pArrTmp = (int*)malloc(nMemSize);
if (pArrList == NULL || pArrTmp ==NULL)
{
return -1;
}
// 初始化数组
for (i = 0; i < nFloor; i++)
{
pArrList[i] = -1;
pArrTmp[i] = i;
}
nLastSize = nFloor;
// 产生随即数，并从pArrTmp表填至pArrList
while (nTotal < nFloor)
{
nRand = rand() % (nFloor -nTotal);
if (pArrTmp[nRand] != -1)
{
pArrList[nTotal] =pArrTmp[nRand];
pArrTmp[nRand] = -1;
nTotal++;
}
else
{
MergArr(pArrTmp,nLastSize);
nLastSize = nFloor -nTotal;
}
}
free(pArrTmp);
pArrTmp = NULL;
return 0;
}
voidMergArr(int* pArr, int nSize)
{
int i = 0;
int total = 0;
for (i = 0; i < nSize; i++)
{
if (pArr[i] != -1)
{
pArr[total] =pArr[i];
if (total != i)
pArr[i] =-1;
total++;
}
}
}