六种排序算法的比较.txt

该文件实现六种排序并进行比较

运行环境TC2.0
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 1000
#define  N 100
#define M 6
#define A 5
typedef  struct record
{int K;
};
 int  cm[6][2];

 select()
{char ch;
int  i,j,t,k;
int a[N];
 printf("***************************\n ");
 printf("请选择初始时数的顺序\n");
 printf("1---完全有序的情况\n");
 printf("2---逆序的情况\n");
 printf("3---随机排序的情况\n");
 printf("0---退出\n");
 printf("***************************\n");
 ch=getch();
 switch(ch)
 {
 case '1': randomize();
 for(i=0;i<N;i++)
 printf("%5d",a[i]=random(MAX));
 for(i=0;i<N-1;i++)
 for(j=i+1;j<N;j++)
 if(a[i]>a[j])
 {t=a[i];
 a[i]=a[j];
 a[j]=t;
 }
 printf("完全有序的数列为:\n");
 for(i=0;i<N;i++)
 printf("%5d",a[i]);
 printf("\n");
 for(i=1;i<7;i++)
{
   printf("请选择排序算法\n");
  printf(" 冒泡排序-------------------1\n");
 printf("  直接插入排序---------------2\n");
 printf("  简单选择排序---------------3\n");
  printf(" 快速排序-------------------4\n");
 printf("  希尔排序-------------------5\n");
  printf(" 堆排序---------------------6\n");
 printf("  退出-----------------------0\n");
 ch=getch();
 switch(ch)
 {case '0':exit(0);
 case'1': Bubblle_sort(a,N);break;
 case'2': Straight_insert_sort(a,N);break;
 case'3': Simple_select_sort(a,N);break;
 case'4': digui(a,0,N-1);break;
 case'5': Shell_sort(a,N);break;
 case'6': Heap_sort(a,N);break;
 default:exit(0);
 }
 }goto loop;
  case '2': randomize();
  for(i=0;i<N;i++)
  printf("%5d",a[i]=random(MAX));
  for(i=0;i<N-1;i++)
  for(j=i+1;j<N;j++)
  if(a[i]<a[j])
  {t=a[i];
  a[i]=a[j];
  a[j]=t;
  }
  printf("逆序的数列为:\n");
  for(i=0;i<N;i++)
  printf("%5d",a[i]);
  printf("\n");
  for(i=0;i<7;i++){
   printf("请选择排序算法\n");
  printf(" 冒泡排序-------------------1\n");
 printf("  直接插入排序---------------2\n");
 printf("  简单选择排序---------------3\n");
  printf(" 快速排序-------------------4\n");
 printf("  希尔排序-------------------5\n");
  printf(" 堆排序---------------------6\n");
 printf("  退出-----------------------0\n");
 ch=getch();
 switch(ch)
 {case '0':exit(0);
 case'1': Bubblle_sort(a,N);break;
 case'2': Straight_insert_sort(a,N);break;
 case'3': Simple_select_sort(a,N);break;
 case'4': digui(a,0,N-1);break;
 case'5': Shell_sort(a,N);break;
 case'6': Heap_sort(a,N);break;
 default:exit(0);
 }
 }break;
  case '3':printf("从0到%d获得%d个随机数:\n",MAX-1,N);
randomize();
for(i=0;i<N;i++)
printf("%5d",a[i]=random(MAX));
for(i=0;i<8;i++){
   printf("请选择排序算法\n");
  printf(" 冒泡排序-------------------1\n");
 printf("  直接插入排序---------------2\n");
 printf("  简单选择排序---------------3\n");
  printf(" 快速排序-------------------4\n");
 printf("  希尔排序-------------------5\n");
  printf(" 堆排序---------------------6\n");
 printf("  退出-----------------------0\n");
 ch=getch();
 switch(ch)
 {case '0':exit(0);
 case'1': Bubblle_sort(a,N);break;
 case'2': Straight_insert_sort(a,N);break;
 case'3': Simple_select_sort(a,N);break;
 case'4': digui(a,0,N-1);break;
 case'5': Shell_sort(a,N);break;
 case'6': Heap_sort(a,N);break;
 default:exit(0);
 }
 }
break;
case '0':exit(0);
default:exit(0);
}
loop:;}
  Bubblle_sort(R,n)
 int R[];
 int n;
{int j,p,h,t;
for(h=n-1;h>0;h=p)
{for(p=j=0;j<h;j++)
{cm[1][0]++;
if(R[j]>R[j+1])
{t=R[j];
R[j]=R[j+1];
R[j+1]=t;

cm[1][1]=cm[1][1]+3;
p=j;}}
}
printf("the data is:\n");
for(j=0;j<n;j++)
printf("%4d",R[j]);
printf("冒泡排序的算法指标为:\n");
printf("比较次数为%d:\n",cm[1][0]);
printf("移动次数为%d:\n",cm[1][1]);
}
  Straight_insert_sort(R,n)
int  R[];
int n;
{int i,j,t;
for(i=1;i<n;i++)
{for(t=R[i],j=i-1;j>=0&&t<R[j];j--)
{R[j+1]=R[j];
cm[2][1]++;}
R[j+1]=t;
cm[2][0]+=i;
}printf("the  sorted data is :\n");
for(i=0;i<n;i++)
printf("%4d",R[i]);
printf("直接插入排序算法的指标为:\n");
printf("比较次数和移动次数分别为%d,%d:\n",cm[2][0],cm[2][1]);
}
Shell_sort(R,n)
int R[];
int n;
{int j,k,h,y;
for(h=n/2;h>0;h=h/2)
{for(j=h;j<n;j++)
{y=R[j];
for(k=j-h;k>=0&&y<R[k];k-=h)
{R[k+h]=R[k];
cm[5][1]++;}
R[k+h]=y;
 }
cm[5][0]=cm[5][0]+n-h;}
printf("the data is:\n");
for(j=0;j<n;j++)
printf("%4d",R[j]);
printf("希尔排序算法的指标为:\n");
printf("比较次数为%d\n",cm[5][0]);
printf("移动次数为%d\n",cm[5][1]);
}

 Simple_select_sort(R,n)
int R[];
int n;
{int t;
int i,j,k;
for(i=0;i<n-1;i++)
{for(k=i,j=i+1;j<n;j++){
cm[3][0]++;
if(R[k]>R[j])
k=j;
if(k!=i)
{t=R[i];
R[i]=R[k];
R[k]=t;
cm[3][1]+=3;
}
}           }
printf("the  data is  \n");
for(j=0;j<n;j++)
printf("%4d",R[j]);
printf("简单选择排序算法的指标为:\n");
printf("比较次数为%d:\n",cm[3][0]);
printf("移动次数为%d:\n",cm[3][1]);
}
 digui(R,p,q)
 int R[];
 int p,q;
{int i;
 Quick_sort(R,p,q);
   for(i=0;i<N;i++)
   printf("%4d",R[i]);
   printf("快速排序算法的指标为:\n");
   printf("比较次数为%d:\n",cm[4][0]);
 printf("  移动次数为%d:\n",cm[4][1]);

 }
 Quick_sort(R,p,q)
 int R[];
  int p,q;
  {int i,j,t;
   if(p<q)
   {i=p;
   j=q;
   t=R[p];
   while(i<j)
   {cm[4][0]=cm[4][0]+1;
   while(i<j&&R[j]>t)j--;
   if(i<j) {R[i++]=R[j]; cm[4][1]++;}
   cm[4][0]=cm[4][0]+1;
   while(i<j&&R[i]<=t)i++;
   if(i<j){R[j--]=R[i]; cm[4][1]++;}
   }
   R[i]=t;
   Quick_sort(R,p,i-1);
   Quick_sort(R,i+1,q);
   }
}
 void create_heap(R,n,L)
 struct record R[];
 int  n,L;
 {int k,j;
 struct record t;
 t=R[L];
 k=L;
 j=2*k+1;
 while(j<n)
 {if(j<n-1&&R[j].K<R[j+1].K)
{ j++;
cm[6][0]++;}
else
cm[6][0]++;
 if(t.K<R[j].K)
 {
 R[k]=R[j];
 cm[6][1]++;
 k=j;
   cm[6][0]++;
 j=2*k+1;
 }else
   break;
 }
 R[k]=t;

 }
   Heap_sort(R,n)
 int R[];
 int  n;
 {int t;
 int i,k;
 for(i=n/2-1;i>=0;i--)
 create_heap(R,n,i);
 for(k=n-1;k>=1;k--)
 {t=R[0];
 R[0]=R[k];
 R[k]=t;cm[6][1]+=3;
 create_heap(R,k,0);
 }
 printf("the data is\n");
 for(i=0;i<n;i++)
 printf("%4d",R[i]);
 printf("堆排序算法的指标为:\n");
 printf("比较次数为%d\n",cm[6][0]);
printf(" 移动次数为%d\n",cm[6][1]);
 }
 void analyse()
 {int  i,j,t;
 printf("这六种排序算法的指标分别为:\n");
 printf("比较次数序列为:\n");
 for(i=0;i<6;i++)
 printf("%4d",cm[i][0]);
 printf("移动次数序列为:\n");
 for(i=0;i<6;i++)
 printf("%4d",cm[i][1]);
 for(j=0;j<5;j++)
 for(i=j+1;i<6;i++)
 if(cm[j][0]>cm[i][0])
 {t=cm[j][0];
 cm[j][0]=cm[i][0];
 cm[i][0]=t;}
 printf("六种排序算法的比较次数有序序列为:\n");
 for(i=0;i<6;i++)
 printf("%4d",cm[i][0]);

  }
main()
{
select();
analyse();
}