#include
#include
#include
#include
#define N 50
void swap
(int *pa, int *pb)
{
int t;
t = *pa;
*pa = *pb;
*pb = t;
}
void select_order(int a[],int n)
{
int
i,j;
int t,min;
for (i=0;i {
min =
a[i];
t = i;
for (j=i+1;j {
if (min > a[j])
{
min = a[j];
t = j;
}
}
if (t != i)
{
swap(a+i,a+t);
}
}
}
int ordered(int
a[],int n)
{
int i;
for (i=0;i {
if
(a[i]>a[i+1])
return 0;
}
return 1;
}
void
disorder(int a[],int n)
{
int i;
int r;
srand((unsigned)time(NULL));
for (i=0;i {
r =
(rand()%(n-i))+i;
swap (a+i,a+r);
}
}
int
equal(int a[],int b[],int n)
{
int *a1,*b1;
a1 =
malloc(sizeof(int)*n);
b1 = malloc(sizeof(int)*n);
memcpy(a1,a,sizeof(int)*n);
memcpy(b1,b,sizeof(int)*n);
select_order(a1,n);
select_order(b1,n);
int i;
int
result;
for (i=0;i {
if (a1[i] != b1[i])
{
result = 0;
break;
}
}
if(i>=n)
result = 1;
free(a1);
free(b1);
return
result;
}
void bubble(int a[],int n)
{
int t,i,j;
for(i=0;i {
for(j=0;j {
if(a[j]>a[j+1])
swap(a+j,a+j+1);
}
}
}
void insertsort(int a[],int n)
{
int key;
int
i,j;
for (i=1;i {
key=a[i];
for(j=i-1;j>=0&&a[j]>key;j--)
{
a[j+1]=a[j];
}
a[j+1]=key;
}
}
int position(int a[],int
l,int r)
{
int i = l+1;
int j = r;
int t;
int key
=a[l];
int key_p = l;
while (i<=j)
{
while((a[j]>=key)&&(i<=j)) j--;
if (i<=j)
{
swap(a+j,a+key_p);
key_p = j;
}
while((a[i] if (i<=j)
{
swap (a+i,a+key_p);
key_p = i;
}
}
return
key_p;
}
void quicksort(int a[],int l,int r)
{
int
key;
if (l>=r) return;
key = position(a,l,r);
quicksort(a,l,key-1);
quicksort(a,key+1,r);
}
int bfind(int
a[],int l,int r,int e)
{
if (l<=r)
{
int mid=
(l+r)/2;
if (a[mid]==e) return mid;
else
{
if(a[mid]>e)
return bfind(a,l,mid-1,e);
else
return bfind(a,mid+1,r,e);
}
}
else
return
-1;
}
int main ()
{
int a[N];
int i;
srand((unsigned)time(NULL));
for (i=0;i a[i] =
rand()%501-250;
for (i=0;i {
printf
("%d:%d\t",i+1,a[i]);
if((i+1)%10==0) printf("\n");
}
printf("ordered:%d\n",ordered(a,N));
int *pa =
malloc(sizeof(int)*N);
memcpy(pa,a,sizeof(int)*N);
printf("disordered by rand:\n");
disorder(a,N);
for
(i=0;i printf ("%d ",a[i]);
printf("\n");
printf("ordered:%d\n",ordered(a,N));
printf ("equal as
before:%d\n",equal(a,pa,N));
free(pa);
printf("Ordered by bubble:\n");
bubble(a,N);
for
(i=0;i printf ("%d ",a[i]);
printf("\n");
printf("ordered:%d\n",ordered(a,N));
printf("disordered by
rand:\n");
disorder(a,N);
for (i=0;i printf ("%d
",a[i]);
printf("\n");
printf("ordered:%d\n",ordered(a,N));
printf("Ordered
by insertsort:\n");
insertsort(a,N);
for (i=0;i
printf ("%d ",a[i]);
printf("\n");
printf("ordered:%d\n",ordered(a,N));
printf("disordered by
rand:\n");
disorder(a,N);
for (i=0;i printf ("%d
",a[i]);
printf("\n");
printf("ordered:%d\n",ordered(a,N));
printf("Ordered
by quicksort:\n");
quicksort(a,0,N-1);
for (i=0;i
{
printf ("%d:%d\t",i+1,a[i]);
if ((i+1)%10==0)
printf("\n");
}
printf("\n");
printf("ordered:%d\n",ordered(a,N));
int pos;
for
(i=0;i {
if(i != bfind(a,0,N-1,a[i]))
{
printf ("test Binary find failed at %d:%d!\n",i+1,a[i]);
}
}
int e;
printf ("Binary Find:");
scanf("%d",&e);
pos = bfind(a,0,N-1,e) + 1;
if(pos)
printf("%d was found at %d\n",e,pos);
else
printf("%d was not
found !\n",e);
return 0;
}
阅读(670) | 评论(0) | 转发(0) |
