兰特阵列 [英] a rand array

问题描述

编写一个获取unsigned数组的函数

用随机值填充所有不同的元素，

并对其进行排序。它应该比qsort更快。


你喜欢我的解决方案吗？

_______________________


#include< ; stdio.h>

#include< stdlib.h>

#include< time.h>


无效

ArrRand（未签名* a，未标注大小，无符号上级）

{static int m = 1;

unsigned i，j，h， temp;


if（a == 0 || size< 2 || superiore == 0）

return;

if（m）

{m = 0; srand（time（0））;}

for（i = 0; i< size; ++ i）

{label：

a [i] = _lrand（）％superiore; / * _ lrand用于Borland * /

for（j = 0; j< i; ++ j）/ *如果没有，请使用your_lrand（）* /

{if（a [i] == a [j]）goto label;

else if（a [i]< a [j]）/ *填充无符号* /

{temp = a [i];

for（h = i; h> j; - h）

a [h] = a [ h - 1];

a [j] = temp;

休息;

}

}

}

}


/ *它是c ++主* /

int main（void）

{unsigned a [100] = {0}，i;


ArrRand（a，（sizeof a）/（sizeof * a），80000000）;

for（i = 0; i< 99; ++ i）

cout<< " " << a [i];

cout<< " \ n";

返回0;

}

解决方案

< blockquote> 2004年5月21日星期五06:07:59 GMT，RoSsIaCrIiLoIA< [e-mail]>写道：

编写一个函数，获取一个unsigned int数组
用随机值填充所有不同的，
并对其进行排序。它应该比qsort更快。

你喜欢我的解决方案吗？
_______________________

#include< stdio.h>
#include< ; stdlib.h>
#include< time.h>

void
ArrRand（无符号* a，未标注大小，无符号上级）
{static int m = 1;
unsigned i，j，h，temp;

if（a == 0 || size< 2 || superiore == 0）
return;
if（m）
{m = 0; srand（time（0））;}
for（i = 0; i< size; ++ i）
{label：
a [i] = _lrand（）％superiore; / * _ lrand用于Borland * /

a [i] =（无符号）_lrand（）％superiore;

< blockquote> RoSsIaCrIiLoIA写道：

写一个函数，获取一个unsigned int数组
用随机值填充所有不同的，
并对其进行排序。它应该比qsort更快。

你喜欢我的解决方案吗？


除了这个代码没有编译的事实，除了微小的数组之外，你永远不会用这种方法击败
qsort。 br />

特别是，将元素插入到

数组中的任意位置是O（N）。由于你为每个元素执行此操作，因此你的算法将具有至少为O（N ^ 2）的时间复杂度。


如果你填充了一个数组随机值，然后传递给qsort，

你会得到O（NlogN）。对于足够大的N值，这几乎每次都会超过
O（N ^ 2）。


应该可以得到一个排序数组随机不同的整数

时间O（N），但不是通过选择随机数和排序。 （

问题说明似乎要求）

_______________________

#include< stdio.h>
#include< stdlib.h>
#include< time.h>

void
ArrRand（unsigned * a，unsiged size，unsigned superiore）
^^^^^ ^^

没有unsiged这样的东西。

{static int m = 1;
unsigned i，j，h，temp;

if（a == 0 || size< 2 || superiore == 0）
return;
if（m）
{m = 0; srand（time（0））;}
for（i = 0; i< size; ++ i）
{label：
a [i] = _lrand（）％superiore; / * _ lrand用于Borland * /
for（j = 0; j< i; ++ j）/ *如果没有，请使用your_lrand（）* /
{if（a [i] = = a [j]）转到标签;


无限循环如果superiore<尺寸。 （如果是b / b
，那就不会致命）


如果你把插入分成一个单独的功能你可以消除

goto并使代码更清晰。但正如我上面所说，插入

这样可能不是你想要做的。

else if（a [i]< a [j]）/ *填写未签字的* /


线性搜索并不是那么好，但在这种情况下并不重要。

{ temp = a [i];
for（h = i; h> j; - h）
a [h] = a [h - 1];


这需要O（N）来插入一个元素并重复N次，使你的算法O（N ^ 2）成为
。 （线性搜索也是如此，但修改需要更少

修改。）

a [j] = temp;
break;
}
}
}
} / *它是一个c ++主* /
int main（无效）
{unsigned a [100] = {0}，i;

ArrRand（a，（sizeof a）/（sizeof * a），80000000）;
for（i = 0; i< 99; ++ i）
cout<< " " << a [i];
cout<< " \\\
英寸;


怎么样的穷人忽略了一个[99]？

返回0;
}

-josh

" RoSsIaCrIiLoIA" < [e-mail]>在留言中写道

新闻：1v ******************************** @ 4ax.com ...

编写一个函数，获取一个unsigned int数组
用随机值填充所有不同的，
并对其进行排序。它应该比qsort更快。

你喜欢我的解决方案吗？

a更快的解决方案就是这样（未经测试）：

#include< time.h>


#define NUM_ELEMENTS 100

int main（void）

{

无符号数组[NUM_ELEMENTS];

无符号值;

int loop;


srand（time（NULL））;


value =（unsigned）rand（）/（RAND_MAX / NUM_ELEMENTS）;


for（loop = 1; loop< NUM_ELEMENTS; loop ++）

{

array [loop] = value;

value + = （未签名）rand（）/（RAND_MAX / NUM_ELEMENTS）;

}


返回0;

}

现在这个方法存在（严重）问题，即你不能准确地告诉

范围的数字，但既然你没有指明，那么这个

符合您的问题。

Allan

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?
_______________________

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void
ArrRand(unsigned* a, unsiged size, unsigned superiore)
{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a[i] == a[j]) goto label;
else if(a[i] < a[j]) /* that fill an unsigned */
{temp = a[i];
for( h = i; h > j; --h)
a[h] = a[h - 1];
a[j] = temp;
break;
}
}
}
}

/* it is a c++ main */
int main(void)
{unsigned a[100] = {0}, i;

ArrRand( a, (sizeof a)/(sizeof *a), 80000000);
for( i = 0; i < 99; ++i)
cout << " " << a[i];
cout << "\n";
return 0;
}

解决方案

On Fri, 21 May 2004 06:07:59 GMT, RoSsIaCrIiLoIA <[e-mail]> wrote:

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?
_______________________

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void
ArrRand(unsigned* a, unsiged size, unsigned superiore)
{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */

a[i] = (unsigned) _lrand() % superiore;

RoSsIaCrIiLoIA wrote:

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?
Aside from the fact that this code doesn''t compile, you''ll never beat
qsort with this method except maybe with tiny arrays.

In particular, inserting an element into an arbitrary position in an
array is O(N). Since you do this for each element, your algorithm will
have time complexity of at least O(N^2).

If you filled an array with random values and then passed that to qsort,
you''d get O(NlogN). For sufficiently large values of N, this will beat
O(N^2) nearly every time.

It should be possible to get a sorted array of random distinct integers
in time O(N), but not by choosing random numbers and sorting. (which
the problem description seems to require)
_______________________

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void
ArrRand(unsigned* a, unsiged size, unsigned superiore) ^^^^^^^
No such thing as unsiged.
{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a[i] == a[j]) goto label;
Infinite loop if superiore < size. (wouldn''t be fatal if it were
documented)

If you split the insertion into a separate function you could eliminate
the goto and make the code more clear. But as I said above, inserting
like this is probably not what you want to do anyway.
else if(a[i] < a[j]) /* that fill an unsigned */
Linear search isn''t all that great, but it doesn''t matter much in this case.
{temp = a[i];
for( h = i; h > j; --h)
a[h] = a[h - 1];
This takes O(N) to insert an element and is repeated N times, making
your algorithm O(N^2). (The linear search does too, but that takes less
modification to fix.)
a[j] = temp;
break;
}
}
}
}

/* it is a c++ main */
int main(void)
{unsigned a[100] = {0}, i;

ArrRand( a, (sizeof a)/(sizeof *a), 80000000);
for( i = 0; i < 99; ++i)
cout << " " << a[i];
cout << "\n";
What about poor neglected a[99]?
return 0;
}

-josh

"RoSsIaCrIiLoIA" <[e-mail]> wrote in message
news:1v********************************@4ax.com...

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?

a much faster solution would be something like this (untested):
#include <time.h>

#define NUM_ELEMENTS 100

int main(void)
{
unsigned array[NUM_ELEMENTS];
unsigned value;
int loop;

srand(time(NULL));

value = (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);

for (loop=1; loop<NUM_ELEMENTS; loop++)
{
array[loop] = value;
value += (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);
}

return 0;
}
Now there are (severe) problems with this method, i.e. you cant tell the
range of the numbers precisely, but since you didn''t specify that, then this
meets your problem.
Allan

这篇关于兰特阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！