排序实验报告.c.txt

通过快速排序

#include "stdio.h"
#include "conio.h"

quicksort(int a[],int l,int r,int *u1,int *v1)                  /*快速排序*/
{
  int i,j,temp,k=0,u,v;
  i=l;   j=r;
  temp=a[i];
  if(l>=r) return;
  while(i!=j)
{
        while(a[j]>=temp&&i<j) j--;
        *u1=*u1+1;
        if(i<j)   { a[i]=a[j]; *v1=*v1+1; i++;}
        while(a[i]<temp&&i<j) i++;
        *u1=*u1+1;
        if(i<j)    {a[j]=a[i];*v1=*v1+1;j--;}
 }
  a[i]=temp;
    
   quicksort(a,l,i-1,u1,v1);
   quicksort(a,i+1,r,u1,v1);
 }
     void shellsort(int a[],int n)   /*希尔排序*/
{
   int d,i,j,x,y , temp,v;
   x=0; y=0 ;

  for(d=n/2;d>0;d=d/2)
{
   for(i=d;i<n;i++)
{
      temp=a[i];
      j=i-d;
      while(j>=0 && temp<a[j])
 {
        a[j+d]=a[j];
        y++;      
        j=j-d; 
  }
         x++ ;
         a[j+d]=temp;

   }
 }
       printf("\n the number of compare x=%d ",x);
  printf("\n the number of move y=%d\n  ",y);
       for(v=0;v<=7;v++)
 {    printf("%5d",a[v]);}
       printf("\n");
}

void binSort(int a[],int n)   /* 折半插入排序 */
{
  int i,j,low,hight,mid,m=0,k =0 ;
  int v;
 int temp;
  for(i=1;i<n;i++)
  {
     temp=a[i];
     low=0;    hight=i-1;
     while(low<=hight)
     {
        mid=(low+hight)/2;
        if (temp<a[mid])
        hight=mid-1;
        else low=mid+1;
            m++;
      }
   for(j=i-1;j>=low;j--)
     a[j+1]=a[j]; k++;
    if(low!=i)   k++;
      a[low]=temp;
   }
   printf("the number of compare m=%d\n",m);
   printf("the number of move k=%d\n",k);
         for(v=0;v<=7;v++)
   {  printf("%8d",a[v]); }
  }
  void main()
{
  int i,j,k,v;
   int *u1=2,*v1 =0;
  int a[8]={11,3,28,52,46,32,66,88};
  int b[8]={11,3,28,52,46,32,66,88};
  int c[8]={11,3,28,52,46,32,66,88};
  printf("binSort\n");
    printf("\n");
  binSort(a,8);
  printf("\n");
    printf("shellSort\n");
     shellsort(b,8);
      printf("\n");
    printf("quickSort\n");
      printf("\n");
   quicksort(c,0,8,u1,v1);
    for(v=0;v<=7;v++)
   {  printf("%5d",a[v]);}


printf("\n the number of compare u1=%d ",*u1);
 printf("\n the number of move v1=%d \n ",*v1);

   getch();
 }