Chinaunix首页 | 论坛 | 博客
  • 博客访问: 639796
  • 博文数量: 263
  • 博客积分: 6000
  • 博客等级: 准将
  • 技术积分: 2555
  • 用 户 组: 普通用户
  • 注册时间: 2008-02-26 11:20
文章分类

全部博文(263)

文章存档

2011年(10)

2010年(19)

2009年(170)

2008年(64)

我的朋友

分类: C/C++

2009-03-23 15:47:32

#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;
}
阅读(688) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~