排序算法比较程序

　　功能要求如下：

　　排序算法比较: shellsort, quicksort, heapsort, mergesort 的算法实现 ，

　　对同样数据集的排序时间比较。

　　源代码：

# include stdio.h
# include time.h
# define MAXSIZE 2000
typedef struct{
　　int key[MAXSIZE];
　　int length;
}list;
long int　compCount;
long int　shiftCount;
void menu(int *m)/*retun m*/
{
　　int i;
　　char menu[6][15]={"1 CREATE ","2 IMPORT ","3 SORT","4 SHOW RESULT",
　　　　　　　　　　　　　 "5 SAVE RESULT","6 EXIT"};
　　clrscr();
　　printf("SORT COMPARE SYSTEMn");
　　for (i=0;i6;i++) printf("%sn",menu[i]);
　　printf("n Please Select (1-6):n");
　 
　　scanf("%d",m);
}
void menusort(int *m)/*retun m*/
{
　　int i;
　　char menusort[5][15]={"1 SHELL SORT","2 QUICK SORT","3 HEAP SORT",
　　　　　　　　　　　　　　"4 MERGE SORT","5 ALL SORT"};
　 
　　clrscr();
　　printf("SORTn");
　　for(i=0;i5;i++) printf("%sn",menusort[i]);
　　printf("n Please Select (1-5):n");
　 
　　scanf("%d",m);
}
void menushow(int *m)/*retun m*/
{
　　int i;
　　char menushow[4][20]={"1 SHELL SORT RESULT","2 QUICK SORT RESULT",
　　　　　　　　　　　　　　"3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
　 
　　clrscr();
　　printf("SHOW SORT RESULTn");
　　for(i=0;i4;i++) printf("%sn",menushow[i]);
　　printf("n Please Select (1-4):n");
　 
　　scanf("%d",m);
}
void menusave(int *m)
{
　　int i;
　　char menusave[4][20]={"1 SHELL SORT RESULT","2 QUICK SORT RESULT",
　　　　　　　　　　　　　 "3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
　 
　　clrscr();
　　printf("SAVE:n");
　　for (i=0;i4;i++) printf("%sn",menusave[i]);
　　printf("n Please Select (1-4):n");
　 
　　scanf("%d",m);
}
void create(list *L)
{
　　int i;
　 
　　printf("HOW MANY DATA？n");
　　scanf("%d",&((*L).length));
　 
　　for(i=1;i=(*L).length;i++)
　　{
　　　　printf("nPLEASE INPUT THE %dth DATA:n",i);
　　　　scanf("%d",&(*L).key[i]);
　　}
　　printf("nCREATE COMPLETE !n");
　　　 
}
int listopen(list *L,char *filename)
{
　　int k=1;
　　FILE *data;
　 
　　data=NULL;
　　data=fopen(filename,"rb");
　 
　　while (! feof(data))
　　　　{
　　　　　　fscanf(data,"%d",&(*L).key[k]);
　　　　　　k++;
　　　　}
　　　　(*L).length=k-1;
}
void import(list *L)/*fix L*/
{
　　char filename[255];
　　int i;
　　printf("nPLEASE INPUT THE FILE PATH AND NAME:n");
　　scanf("%s",filename);
　　clrscr();
　　listopen(L,filename);
　　for(i=1;i(*L).length;i++) printf("%d ",(*L).key[i]);
　　printf("nPRESS ANYKEY RETURN TO MAINMENU...n");
　　getch();
}
void save(list L)
{
　　FILE *data;
　　char filename[255];
　　int r;
　　printf("nPLEASE INPUT THE FILE PATH AND NAME:n");
　　scanf("%s",filename);
　　data=fopen(filename,"wb");
　　for(r=1;r=L.length;r++) fprintf(data,"%dn",L.key[r]);
　　fclose(data);
　　printf("SAVE OK! n PRESS ANY KEY TO RETURN THE MAINMENU... ");
　　getch();
　　　 
}
list shellsort(list L)/*retun L_SHELL*/
{
　　int i,j,gap,x,n;
　 
　　compCount=shiftCount=0;
　　n=L.length;
　　gap=n/2;
　　while (gap0)
　　{
　　　　compCount++;
　　　　for(i=gap+1;i=n;i++)
　　　　{
　　　　　　compCount++;
　　　　　　j=i-gap;
　　　　　　while(j0)
　　　　　　{
　　　　　　　　compCount++;
　　　　　　　　if(L.key[j]L.key[j+gap])
　　　　　　　　{
　　　　　　　　　　compCount++;
　　　　　　　　　　x=L.key[j];shiftCount++;
　　　　　　　　　　L.key[j]=L.key[j+gap];shiftCount++;
　　　　　　　　　　L.key[j+gap]=x;shiftCount++;
　　　　　　　　　　j=j-gap;
　　　　　　　　}
　　　　　　　　else j=0;
　　　　　　}
　　　　　　　 
　　　　}
　　　　gap=gap/2;
　　}
　　return L;
}
void shell(list L,list *LS,float *timeshell)/*return LS,timeshell.
　　　　　　　　　　　　　　　　　　　　　　　 MUST add an "getch"!!*/
{
　　clock_t start,end;
　 
　　　 
　　start=clock();
　　(*LS)=shellsort(L);
　　end=clock();
　 
　　*timeshell=(end-start)/CLK_TCK;
　 
　　printf("nSHELLSORT COST TIME :%f SECONDS.",*timeshell);
　　printf("Compare %d times.Shfit %d times.n",compCount,shiftCount);
}
int Partition(list * pL,int low,int high)
{
　　int pivotkey;
　　pL-key[0]=pL-key[low];shiftCount++;
　　pivotkey=pL-key[low];shiftCount++;
　　while(lowhigh)
　　{
　　　　compCount++;
　　　　while(lowhigh && pivotkey=(pL-key[high]))
　　　　　　 {compCount++;compCount++; --high;}
　　　　pL-key[low]=pL-key[high];shiftCount++;
　　　　while(lowhigh && (pL-key[low])=pivotkey)
　　　　　　 {compCount++;compCount++; ++low;}
　　　　pL-key[high]=pL-key[low];shiftCount++;
　　}
　　pL-key[low]=pL-key[0];shiftCount++;
　　return low;
}/*Partition*/
void QSort(list * pL,int low,int high)
{
　　int pivotloc;
　　if(lowhigh)
　　{
　　　　compCount++;
　　　　pivotloc=Partition(pL,low,high);
　　　　QSort(pL,low,pivotloc-1);
　　QSort(pL,pivotloc+1,high);
　　}
}/*QSort*/
list QuickSort(list pL)
{
　　compCount=shiftCount=0;
　　QSort(&pL,1,pL.length);
　　return pL;
}/*QuickSort*/
void quick(list L,list *LQ,float *timequick)/*MUST add an "getch"!!*/
{
　　clock_t start,end;
　　start=clock();
　　(*LQ)=QuickSort(L);
　　end=clock();
　 
　　*timequick=(end-start)/CLK_TCK;
　 
　　printf("nQUICKSORT COST TIME :%f SECONDS.",*timequick);
　　printf("Compare %d times.Shfit %d times.n",compCount,shiftCount);
}
void sift(list L,int l,int m)
{
　　int i,j,x;
　　i=l;
　　j=2*i;
　　x=L.key[i];
　　while (j=m)
　　{
　　　　compCount++;
　　　　if(jm && L.key[j]L.key[j+1]) {j++;compCount++;compCount++;}
　　　　if(xL.key[j])
　　　　{
　　　　　　compCount++;
　　　　　　L.key[i]=L.key[j];shiftCount++;
　　　　　　i=j;shiftCount++;
　　　　　　j=2*i;
　　　　}
　　　　else j=m+1;
　　}
　　L.key[i]=x;shiftCount++;
}
list heapsort(list L)
{
　　int i,w;
　 
　　compCount=shiftCount=0;
　　for (i=L.length/2;i=1;i--) {sift(L,i,L.length);compCount++;}
　　for (i=L.length;i=2;i--)
　　{
　　　　compCount++;
　　　　w=L.key[i];shiftCount++;
　　　　L.key[i]=L.key[1];shiftCount++;
　　　　L.key[1]=w;shiftCount++;
　　　　sift(L,i-1,1);
　　}
　　return L;
}
void heap(list L,list *LH,float *timeheap)
{
　　clock_t start,end;
　 
　　　 
　　start=clock();
　　(*LH)=heapsort(L);
　　end=clock();
　 
　　*timeheap=(end-start)/CLK_TCK;
　 
　　printf("nHEAPSORT COST TIME :%f SECONDS.",*timeheap);
　　printf("Compare %d times.Shfit %d times.n",compCount,shiftCount);
}
void Merge(int source[],int result[],int size,int n)
{
　　int lb1,lb2,ub1,ub2,p,i,j;
　　lb1=0;
　　p=0;
　　while((lb1+size)n)
　　{
　　　　compCount++;
　　　　lb2=lb1+size;
　　　　ub1=lb2-1;
　　　　if((lb2+size-1)n)
　　　　　 { ub2=n-1; compCount++; shiftCount++;}
　　　　else
　　　　　 {ub2=lb2+size-1; compCount++; shiftCount++;}
　　　　i=lb1;
　　　　j=lb2;
　　　　while((i=ub1)&&(j=ub2))
　　　　　　{
　　　　　　　　compCount++;compCount++;
　　　　　　　　if(source[i]=source[j])
　　　　　　　　　　{result[p++]=source[i++]; shiftCount++; compCount++;}
　　　　　　　　else
　　　　　　　　　　{result[p++]=source[j++]; shiftCount++; compCount++;}
　　　　　　}
　　　　while(i=ub1)
　　　　　　{result[p++]=source[i++]; shiftCount++; compCount++;}
　　　　while(j=ub2)
　　　　　　{result[p++]=source[j++]; shiftCount++; compCount++;}
　　　　lb1=ub2+1;
　　}
　　i=lb1;
　　while(pn)
　　　 {compCount++; result[p++]=source[i++];shiftCount++;}
}
void Mergesort(list *L)
{
　　int n=(*L).length;
　　int s=1;
　　int *temp=(int *)malloc(n*sizeof(int));
　　compCount=shiftCount=0;
　 
　　if (temp==NULL)
　　{
　　　　printf("out of memory");
　　　　return;
　　}
　　while(sn)
　　{
　　compCount++;
　　Merge((*L).key,temp,s,n);
　　　　s*=2;
　　Merge(temp,(*L).key,s,n);
　　　　s*=2;
　　}
　　compCount++;
}
void domerge(list L,list *LM,float *timemerge)/*MUST add an "getch"!!*/
{
　　clock_t start,end;
　　start=clock();
　　Mergesort(&L);
　 
　　end=clock();
　　(*LM)=L;
　　*timemerge=(end-start)/CLK_TCK;
　 
　　printf("nMERGESORT COST TIME :%f SECONDS.",*timemerge);
　　printf("Compare %d times.Shfit %d times.n",compCount,shiftCount);
}
main()
{
　　list L,LS,LQ,LH,LM;
　　int LOCK3=0,LOCK4=0,LOCK5=0,RUN=1,LOCK41=0,LOCK42=0,LOCK43=0,LOCK44=0;
　　int comd,r;
　　float timeshell,timequick,timeheap,timemerge;
　 
　　while(RUN==1)
　　{
start:
　　　　menu(&comd);
　　　　switch (comd)
　　　　{
　　　　　　case 1:
　　　　　　　　create(&L);
　　　　　　　　LOCK3=1;
　　　　　　　　break;
　　　　　　case 2:
　　　　　　　　import(&L);
　　　　　　　　LOCK3=1;
　　　　　　　　goto start;
　　　　　　case 3:
　　　　　　　　if(LOCK3==0) goto start;
　　　　　　　　menusort(&comd);
　　　　　　　　LOCK4=1;
　　　　　　　　LOCK5=1;
　　　　　　　　switch (comd)
　　　　　　　　{
　　　　　　　　 case 1:
　　　　　　　　　　LOCK41=1;
　　　　　　　　　　shell(L,&LS,&timeshell);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 2:
　　　　　　　　　　LOCK42=1;
　　　　　　　　　　quick(L,&LQ,&timequick);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 3:
　　　　　　　　　　LOCK43=1;
　　　　　　　　　　heap(L,&LH,&timeheap);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 4:
　　　　　　　　　　LOCK44=1;
　　　　　　　　　　domerge(L,&LM,&timemerge);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 5:
　　　　　　　　　　LOCK41=1;
　　　　　　　　　　LOCK42=1;
　　　　　　　　　　LOCK43=1;
　　　　　　　　　　LOCK44=1;
　　　　　　　　　　shell(L,&LS,&timeshell);
　　　　　　　　　　quick(L,&LQ,&timequick);
　　　　　　　　　　heap(L,&LH,&timeheap);
　　　　　　　　　　domerge(L,&LM,&timemerge);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 6:
　　　　　　　　　　goto start;
　　　　　　　　}
　　　　　　case 4:
　　　　　　　　if(LOCK4==0) goto start;
　　　　　　　　menushow(&comd);
　　　　　　　　switch(comd)
　　　　　　　　{
　　　　　　　　 case 1:
　　　　　　　　　　if(LOCK41==0) goto start;
　　　　　　　　　　for (r=1;r=LS.length;r++)
　　　　　　　　　　　　 printf("%d",LS.key[r]);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 2:
　　　　　　　　　　if(LOCK42==0) goto start;
　　　　　　　　　　for (r=1;r=LQ.length;r++)
　　　　　　　　　　　　 printf("%d",LQ.key[r]);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 3:
　　　　　　　　　　if(LOCK43==0) goto start;
　　　　　　　　　　for (r=1;r=LH.length;r++)
　　　　　　　　　　　　 printf("%d",LH.key[r]);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 4:
　　　　　　　　　　if(LOCK44==0) goto start;
　　　　　　　　　　for (r=1;r=LM.length;r++)
　　　　　　　　　　　　 printf("%d",LM.key[r]);
　　　　　　　　　　printf("n PRESS ANY KEY TO RETURN MAIN MENU... n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 6:
　　　　　　　　　　goto start;
　　　　　　　　}
　　　　　　case 5:
　　　　　　　　if(LOCK5==0) goto start;
　　　　　　　　menusave(&comd);
　　　　　　　　switch (comd)
　　　　　　　　{
　　　　　　　 
　　　　　　　　　　case 1:
　　　　　　　　　　　　if(LOCK41==0) goto start;
　　　　　　　　　　　　save(LS);
　　　　　　　　　　　　break;
　　　　　　　　　　case 2:
　　　　　　　　　　　　if(LOCK42==0) goto start;
　　　　　　　　　　　　save(LQ);
　　　　　　　　　　　　break;
　　　　　　　　　　case 3:
　　　　　　　　　　　　if(LOCK43==0) goto start;
　　　　　　　　　　　　save(LH);
　　　　　　　　　　　　break;
　　　　　　　　　　case 4:
　　　　　　　　　　　　if(LOCK44==0) goto start;
　　　　　　　　　　　　save(LM);
　　　　　　　　　　　　break;
　　　　　　　　　　case 6:
　　　　　　　　　　　　break;
　　　　　　　　　　　 
　　　　　　　　}
　　　　　　　　break;
　　　　　　case 6:
　　　　　　　　exit(0);
　　　　}
　 
　　}　 
　 
}