operation.h

对输入的一组数据进行插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序

//直接插入排序 
void Insertsort() 
{ 
 int i,j,k,m=0; 
  printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t"); 
 for(k=1;k<=L;k++) 
{ 
   printf("%5d",R[k].key); 
} 
getchar(); 
   printf("\n"); 
     for(i=2;i<=L;i++) 
	 { 
       if(R[i].key<R[i-1].key) 
	   { 
      R[0]=R[i]; 
      j=i-1; 
      while(R[0].key<R[j].key) 
	  { 
        R[j+1]=R[j]; 
        j--; 
	  } 
      R[j+1]=R[0]; 
	   } 
     m++; 
     printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",m); 
     for(k=1;k<=L;k++)  
	 { 
    printf("%5d",R[k].key);
	 } 
 getchar(); 
 printf("\n"); 
	 } 
printf("\n\t\t排序最终结果是：\n\t\t"); 
 for(i=1;i<=L;i++) 
 { 
  printf("%5d",R[i].key); 
 }  
 printf("\n"); 
} 

//希尔排序 
void Shellsort() 
{ 
   int i,j,gap,x,m=0,k; 
    printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t"); 
    for(k=1;k<=L;k++) 
	{ 
      printf("%5d",R[k].key); 
	} 
 getchar();  
 printf("\n"); 
 gap=L/2; 
 while(gap>0) 
 { 
  for(i=gap+1;i<=L;i++) 
  { 
    j=i-gap; 
 while(j>0) 
 { 
   if(R[j].key>R[j+gap].key) 
   { 
    x=R[j].key; 
    R[j].key=R[j+gap].key; 
    R[j+gap].key=x; 
    j=j-gap; 
   } 
  else 
  { 
   j=0; 
  } 
 } 
} 
    gap=gap/2;  
    m++; 
    printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",m); 
    for(k=1;k<=L;k++) 
	{ 
      printf("%5d",R[k].key); 
	} 
  getchar(); 
  printf("\n"); 
 } 
   printf("\n\t\t排序最终结果是：\n\t\t"); 
   for(i=1;i<=L;i++) 
   { 
    printf("%5d",R[i].key); 
   } 
    printf("\n"); 
} 

//冒泡排序 
void Bubblesort() 
{ 
   int i,j,k;  
   int exchange; 
   printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t"); 
     for(k=1;k<=L;k++) 
	 { 
       printf("%5d",R[k].key); 
	 } 
    getchar(); 
    printf("\n"); 
  for(i=1;i<L;i++) 
  { 
    exchange=FALSE; 
    for(j=L;j>=i+1;j--) 
	{ 
      if(R[j].key<R[j-1].key) 
	  { 
         R[0].key=R[j].key; 
         R[j].key=R[j-1].key; 
         R[j-1].key=R[0].key; 
         exchange=TRUE; 
	  } 
	} 
      if(exchange) 
	  { 
          printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",i); 
          for(k=1;k<=L;k++) 
		  { 
            printf("%5d",R[k].key); 
		  } 
   getchar(); 
  printf("\n"); 
	  } 
  } 
   printf("\n\t\t排序最终结果是：\n\t\t"); 
   for(i=1;i<=L;i++) 
   { 
     printf("%5d",R[i].key); 
   } 
     printf("\n"); 
} 

int Partition(int i,int j) //i和j为形式参数，分别代表low和high 
{ 
  RecType pirot=R[i]; 
  while(i<j) 
  { 
    while(i<j&&R[j].key>=pirot.key) 
	{ 
      j--; 
	} 
     if(i<j) 
	 { 
         R[i++]=R[j]; 
	 } 
       while(i<j&&R[j].key<=pirot.key) 
	   { 
         i++;  
	   } 
    if(i<j) 
	{ 
      R[j--]=R[i]; 
	} 
  } 
  R[i]=pirot; 
return i; 
} 

//递归排序 
void Quicksort(int low,int high) 
{ 
   int pirotpos,k; 
   if(low<high) 
   { 
     pirotpos=Partition(low,high); 
     num++; 
     printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",num); 
     for(k=1;k<=L;k++) 
	 { 
       printf("%5d",R[k].key); 
	 } 
     getchar(); 
     printf("\n"); 
     Quicksort(low,pirotpos-1); 
     Quicksort(pirotpos+1,high); 
   } 
}
 
//选择排序 
void Selectsort() 
{ 
    int i,j,k,h; 
    printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t"); 
    for(k=1;k<=L;k++) 
	{ 
      printf("%5d",R[k].key); 
	} 
    getchar(); 
    printf("\n"); 
    for(i=1;i<L;i++) 
	{ 
      h=i; 
      for(j=i+1;j<=L;j++) 
	  { 
        if(R[j].key<R[h].key) 
		{ 
          h=j; 
		} 
	  } 
      if(h!=j) 
	  { 
        R[0]=R[i]; 
        R[i]=R[h]; 
        R[h]=R[0]; 
	  } 
         printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",i); 
         for(k=1;k<=L;k++) 
		 { 
           printf("%5d",R[k].key); 
		 } 
     getchar(); 
     printf("\n"); 
	} 
     printf("\n\t\t排序最终结果是：\n\t\t"); 
     for(i=1;i<=L;i++) 
	 { 
        printf("%5d",R[i].key); 
	 } 
        printf("\n"); 
} 

void Merge(int low,int mm,int high) 
{ 
    int i=low,j=mm+1,p=0; 
    RecType *R1; 
    R1=new RecType[high-low+1]; 
    if(!R1) 
	{ 
      printf("内存不足！"); 
	} 
      while(i<=mm&&j<=high)  
	  { 
        R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++]; 
	  } 
      while(i<=mm) 
	  { 
        R1[p++]=R[i++]; 
	  } 
      while(j<=high) 
	  { 
        R1[p++]=R[j++]; 
	  } 
          for(p=0,i=low;i<=high;p++,i++) 
		  { 
           R[i]=R1[p]; 
		  } 
} 

void MergePass(int length) 
{ 
   int i; 
   for(i=1;i+2*length-1<=L;i=i+2*length) 
   { 
      Merge(i,i+length-1,i+2*length-1); 
   } 
      if(i+length-1<L) 
	  { 
        Merge(i,i+length-1,L); 
	  } 
} 

//归并排序 
void Mergesort() 
{ 
    int length,k,m=0,i; 
    printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t"); 
    for(k=1;k<=L;k++) 
	{ 
      printf("%5d",R[k].key); 
	} 
      getchar(); 
      printf("\n"); 
      for(length=1;length<L;length*=2) 
	  { 
        MergePass(length); 
        m++; 
        printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",m); 
        for(k=1;k<=L;k++) 
		{ 
           printf("%5d",R[k].key); 
		} 
        getchar(); 
        printf("\n"); 
	  } 
     printf("\n\t\t排序最终结果是：\n\t\t"); 
     for(i=1;i<=L;i++) 
	 { 
         printf("%5d",R[i].key); 
	 } 
     printf("\n"); 
} 

//堆建 
void CreateHeap(int root,int index) 
{ 
  int j,temp,finish; 
  j=2*root; 
  temp=R[root].key; 
  finish=0; 
    while(j<=index&&finish==0) 
	{ 
      if(j<index) 
	  { 
        if(R[j].key<R[j+1].key) 
		{ 
          j++; 
		} 
	  } 
      if(temp>=R[j].key) 
	  { 
         finish=1; 
	  } 
    else 
	{ 
       R[j/2].key=R[j].key; 
       j=j*2; 
	} 
	} 
      R[j/2].key=temp; 
} 
//堆排序 
void Heapsort() 
{ 
   int i,j,temp,k; 
   for(i=(L/2);i>=1;i--) 
   { 
      CreateHeap(i,L); 
   } 
   for(i=L-1,k=1;i>=1;i--,k++) 
   { 
     temp=R[i+1].key; 
     R[i+1].key=R[1].key; 
     R[1].key=temp; 
     CreateHeap(1,i); 
     printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",k); 
     for(j=1;j<=L;j++) 
	 { 
       printf("%5d",R[j].key); 
	 } 
     getchar();  
     printf("\n"); 
   } 
} 
void Heap() 
{ 
    int i; 
    printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t"); 
    for(i=1;i<=L;i++) 
	{ 
      printf("%5d",R[i].key); 
	} 
    getchar(); 
    printf("\n"); 
    Heapsort(); 
    printf("\n\t\t排序最终结果是：\n\t\t");  
    for(i=1;i<=L;i++) 
	{ 
     printf("%5d",R[i].key); 
	} 
     printf("\n"); 
}