排序算法对比程序[VC/C++编程]

功效要求以下:

排序算法对比: 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 SYSTEM\n");
　　for (i=0;i<6;i++) printf("%s\n",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("SORT\n");
　　for(i=0;i<5;i++) printf("%s\n",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 RESULT\n");
　　for(i=0;i<4;i++) printf("%s\n",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;i<4;i++) printf("%s\n",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,"%d\n",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 (gap>0)
　　{
　　　　compCount++;
　　　　for(i=gap+1;i<=n;i++)
　　　　{
　　　　　　compCount++;
　　　　　　j=i-gap;
　　　　　　while(j>0)
　　　　　　{
　　　　　　　　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(low<high)
　　{
　　　　compCount++;
　　　　while(low<high && pivotkey<=(pL->key[high]))
　　　　　　 {compCount++;compCount++; --high;}
　　　　pL->key[low]=pL->key[high];shiftCount++;
　　　　while(low<high && (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(low<high)
　　{
　　　　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(j<m && L.key[j]<L.key[j+1]) {j++;compCount++;compCount++;}
　　　　if(x<L.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(p<n)
　　　 {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(s<n)
　　{
　　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,×hell);
　　　　　　　　　　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,×hell);
　　　　　　　　　　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);
　　　　}
　 
　　}　 
　 
}