最近一直搞數據庫，很久沒摸C語言，都快忘了。為了練手，前段時間一個沒有完成的產生不重復隨機序列的算法重寫一遍。
C語言沒有隨機種子值的概念，所以產生一個隨機、不重復序列還不太容易。最常歸的思路是：給定一個范圍，然後做rand() %MAX_VALUE運算，如果發現該值已經取過，則重新產生一個值。這個算法，你會發現隨著，當MAX_VALUE值大到一定程度時（我的測試值為20），就會陷入死循環。原因是，比如20個數，取了前面18個數，產生後面兩個數的幾率就會指數及減小，可能做上百萬次運算，也無法產生最後兩個數。於是自己重新想了一種算法。
算法原理：給出兩個數列，產生一個隨機數，將第二個數列該位置上的數，復制到第一個數列，然後對第二個數列進行壓縮，知道所有的值都使用完為止。如圖：
第一輪迭代
將臨時數列進行壓縮，進行第二輪迭代：
這樣，基本可以產生一個均勻不重復的隨機數列。但是，根據測試結果，同一個MAX_VALUE值，每次產生的隨機數列是一樣的，所以，若將此應用於生產，還需做其他處理。
源代碼如下：
#include"stdafx.h"
#include<stdlib.h>
#include<stdio.h>
#include<memory.h>
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++;
}
}
}
