生成方案1：
产生第i个随机数，逐个检查之前产生过的随机数（a[0]~a[i-1]) 是否有重复，无重复则放进数组a[i]，若有则得新产生，直到没有重复为止。缺点是效率太低，在检测 重复性的问题 上耗费太多。时间复杂度为O(n^3)。
#include
#include
#include
#include
#include /*
* a[]: 放置随机数的起始地址
* size:要产生的随机数的个数(数组大小)
* start:要产生的随机数n的范围,大于等于start
* end:要产生的随机数n的范围,小于end
*/
void rand_gen(int a[], int size, int start, int end )
{
int n,i,k ;
int ok = 1;
for( i = 0;
i<=size-1;
i++ )
{
//如果n与a[0]到a[i-1]的任何值有重复，
//就一直产生随机数,直到不重复
while(1)
{
n = rand() % (end-start) + start ;
ok = 1;
//假设不重复//从a[0]到a[i-1],检测是否有重复
for(k=0;
k<= i-1;
k++ )
{
if( a[k] == n )
{
ok = 0;
break;
//检测到重复
}
} if( ok )
{
a[i] = n;
//没有重复，把n放入数组
break ;
}
}//退出do while，继续第i+1个随机数
}
} 生成方案2：
用一个1000 0000个元素的“数组”， 记录每个数字是否产生。 flag[n] == 1表示n已经存在，为0不存在。这种方案适用于范围较小的情形。时间复杂度O(n)，空间复杂度算O(n)吧。内存消耗有点大，实测0.2秒左右
/*
* 申请一块动态内存，1千万字节(大概10MB,比较大)
* 每个字节记录一个数的有无,刚好覆盖[0,1000 0000)
* flag[n]==1，表示随机数n已经产生
* flag[n]==0, 表示随机数n还没有产生过
*/
void rand_gen2(int a[], int size, int start, int end )
{
int n,i,k ;
char * flag = NULL;
flag = (char*)malloc(end);
//将来测试时end设为1000 0000
if( NULL == flag )
{
perror("memory for flag failed");
return ;
}
memset(flag, 0, end);
//初始化为全0 //产生size个随机数
for( i = 0;
i生成方案3：
与方案2原理一样，只不过用二进位来记录，节约了一点内存。时间复杂度O(n)，空间复杂度也算O(n)，内存占用1.25MB。
/*
* 用二进位来标示一个随机数是否已经产生,
* 一个字节记录8个数,节约了内存
* 例：flag指向一块动态内存，
* 第0个字节第6位(1或0)记录6是否产生
* 第1个字节第6位(1或0)记录14是否产生
*/
void rand_gen3(int a[], int size, int start, int end )
{
int n,i,k ;
char * flag = NULL;
flag = (char*)malloc(end/8+1);
if( NULL == flag )
{
perror("Memory for flag failed");
return ;
}
memset(flag, 0, end/8+1);
for( i = 0;
i<=size-1;
i++ )
{
//一直产生随机数,直到不重复
while(1)
{
n = rand() % (end-start) + start ;
//对于n来说，它的记录在第n/8个字节里的第n%8位
//为0表示没有产生过，1表示已经产生
if( 0 == (flag[n/8] & 1<<(n%8)) )
{
a[i] = n;
//没有重复，把n放入数组
flag[n/8] = flag[n/8] | ( 1<<(n%8) );
//将n对应记录位 置1
break ;
}
}//退出do while，继续第i+1个随机数
} free(flag);
}排序方案1：
与生成方案2类似申请一块动态内存，对于所有数，使用一大的flag数组， flag[n]==1，表示随机数n存在，flag[n]==0, 表示随机数n不存在。
先将数组过一遍，将每个数是否存在统计到flag中去，
再从flag的前面开始，发现flag[n]为1的就依次把n输出到数组中去。时间复杂度O(n)，内存消耗较大
/*
* 申请一块动态内存，1千万字节(大概10MB,比较大)
* 每个字节记录一个数的有无,刚好覆盖[0,1000 0000)
* flag[n]==1，表示n在数组a[]中
* flag[n]==0, 表示n不在数组中
* 记录完成后再从flag的前面往后面检查
* 若flag[n]为1，就将n依次输出到数组中去
*/
void sort( int a[], int size)
{
int i,k ;
char * flag = NULL;
flag = (char*)malloc(10000000);
if( NULL == flag )
{
perror("memory for flag failed");
return ;
}
memset(flag, 0, 10000000);
//全部初始化为0 for(i=0;
i排序方案2：
排序方案1的改进版，用二进位来记录，减小内存消耗。
/*
* 用二进位来标示一个随机数是否存在,
* 一个字节记录可8个数,节约了内存
* 例：flag指向一块动态内存，
* 第0个字节第6位为1记录6 存在
* 第1个字节第6位为0记录14不存在
*/
void sort2( int a[], int size)
{
int i,k ;
char * flag = NULL;
flag = (char*)malloc(10000000/8+1);
if( NULL == flag )
{
perror("memory for flag failed");
return ;
}
memset(flag, 0, 10000000/8+1);
//全部初始化为0 for(i=0;
i主函数
int main()
{
// 0->1000 0000
int i,n;
int a[1000000] = {0};
//在栈上申请这么大个数组居然通过了 srand(time(NULL));
rand_gen3(a,1000000, 0, 10000000);
//产生随机数 for( i=0;
i<1000;
i++ )
{
printf("%d ", a[i]);
}
printf("\n");
printf("=======================================\n");
sort2(a, 1000000);
//排序 for( i=0;
i<1000;
i++ )
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
【生成及排序一百万个不重复的随机数，随机数范围|生成及排序一百万个不重复的随机数，随机数范围 [0, 1000 0000)】
