功能要求如下：
排序算法比較: 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",
/t/t/t "5 SAVE RESULT","6 EXIT"};
clrscr();
printf("SORT COMPARE SYSTEM");
for (i=0;i<6;i++) printf("%s",menu);
printf(" Please Select (1-6):");
scanf("%d",m);
}
void menusort(int *m)/*retun m*/
{
int i;
char menusort[5][15]={"1 SHELL SORT","2 QUICK SORT","3 HEAP SORT",
/t/t/t "4 MERGE SORT","5 ALL SORT"};
clrscr();
printf("SORT");
for(i=0;i<5;i++) printf("%s",menusort);
printf(" Please Select (1-5):");
scanf("%d",m);
}
void menushow(int *m)/*retun m*/
{
int i;
char menushow[4][20]={"1 SHELL SORT RESULT","2 QUICK SORT RESULT",
/t/t/t "3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
clrscr();
printf("SHOW SORT RESULT");
for(i=0;i<4;i++) printf("%s",menushow);
printf(" Please Select (1-4):");
scanf("%d",m);
}
void menusave(int *m)
{
int i;
char menusave[4][20]={"1 SHELL SORT RESULT","2 QUICK SORT RESULT",
/t/t/t "3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
clrscr();
printf("SAVE:");
for (i=0;i<4;i++) printf("%s",menusave);
printf(" Please Select (1-4):");
scanf("%d",m);
}
void create(list *L)
{
int i;
printf("HOW MANY DATA?");
scanf("%d",&((*L).length));
for(i=1;i<=(*L).length;i++)
{
/tprintf("PLEASE INPUT THE %dth DATA:",i);
/tscanf("%d",&(*L).key);
}
printf("CREATE COMPLETE !");
/t
}
int listopen(list *L,char *filename)
{
int k=1;
FILE *data;
data=NULL;
data=fopen(filename,"rb");
while (! feof(data))
/t{
/t fscanf(data,"%d",&(*L).key[k]);
/t k++;
/t}
/t(*L).length=k-1;
}
void import(list *L)/*fix L*/
{
char filename[255];
int i;
printf("PLEASE INPUT THE FILE PATH AND NAME:");
scanf("%s",filename);
clrscr();
listopen(L,filename);
for(i=1;i<(*L).length;i++) printf("%d ",(*L).key);
printf("PRESS ANYKEY RETURN TO MAINMENU...");
getch();
}
void save(list L)
{
FILE *data;
char filename[255];
int r;
printf("PLEASE INPUT THE FILE PATH AND NAME:");
scanf("%s",filename);
data=fopen(filename,"wb");
for(r=1;r<=L.length;r++) fprintf(data,"%d",L.key[r]);
fclose(data);
printf("SAVE OK! PRESS ANY KEY TO RETURN THE MAINMENU... ");
getch();
/t
}
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)
{
/tcompCount++;
/tfor(i=gap+1;i<=n;i++)
/t{
/t compCount++;
/t j=i-gap;
/t while(j>0)
/t {
/t/tcompCount++;
/t/tif(L.key[j]>L.key[j+gap])
/t/t{
/t/t compCount++;
/t/t x=L.key[j];shiftCount++;
/t/t L.key[j]=L.key[j+gap];shiftCount++;
/t/t L.key[j+gap]=x;shiftCount++;
/t/t j=j-gap;
/t/t}
/t/telse j=0;
/t }
/t/t
/t}
/tgap=gap/2;
}
return L;
}
void shell(list L,list *LS,float *timeshell)/*return LS,timeshell.
/t/t/t/t/t MUST add an "getch"!!*/
{
clock_t start,end;
/t
start=clock();
(*LS)=shellsort(L);
end=clock();
*timeshell=(end-start)/CLK_TCK;
printf("SHELLSORT COST TIME :%f SECONDS.",*timeshell);
printf("Compare %d times.Shfit %d times.",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)
{
/tcompCount++;
/twhile(low<high && pivotkey<=(pL->key[high]))
/t {compCount++;compCount++; --high;}
/tpL->key[low]=pL->key[high];shiftCount++;
/twhile(low<high && (pL->key[low])<=pivotkey)
/t {compCount++;compCount++; ++low;}
/tpL->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)
{
/tcompCount++;
/tpivotloc=Partition(pL,low,high);
/tQSort(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("QUICKSORT COST TIME :%f SECONDS.",*timequick);
printf("Compare %d times.Shfit %d times.",compCount,shiftCount);
}
void sift(list L,int l,int m)
{
int i,j,x;
i=l;
j=2*i;
x=L.key;
while (j<=m)
{
/tcompCount++;
/tif(j<m && L.key[j]<L.key[j+1]) {j++;compCount++;compCount++;}
/tif(x<L.key[j])
/t{
/t compCount++;
/t L.key=L.key[j];shiftCount++;
/t i=j;shiftCount++;
/t j=2*i;
/t}
/telse j=m+1;
}
L.key=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--)
{
/tcompCount++;
/tw=L.key;shiftCount++;
/tL.key=L.key[1];shiftCount++;
/tL.key[1]=w;shiftCount++;
/tsift(L,i-1,1);
}
return L;
}
void heap(list L,list *LH,float *timeheap)
{
clock_t start,end;
/t
start=clock();
(*LH)=heapsort(L);
end=clock();
*timeheap=(end-start)/CLK_TCK;
printf("HEAPSORT COST TIME :%f SECONDS.",*timeheap);
printf("Compare %d times.Shfit %d times.",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)
{
/tcompCount++;
/tlb2=lb1+size;
/tub1=lb2-1;
/tif((lb2+size-1)>n)
/t { ub2=n-1; compCount++; shiftCount++;}
/telse
/t {ub2=lb2+size-1; compCount++; shiftCount++;}
/ti=lb1;
/tj=lb2;
/twhile((i<=ub1)&&(j<=ub2))
/t {
/t/tcompCount++;compCount++;
/t/tif(source<=source[j])
/t/t {result[p++]=source[i++]; shiftCount++; compCount++;}
/t/telse
/t/t {result[p++]=source[j++]; shiftCount++; compCount++;}
/t }
/twhile(i<=ub1)
/t {result[p++]=source[i++]; shiftCount++; compCount++;}
/twhile(j<=ub2)
/t {result[p++]=source[j++]; shiftCount++; compCount++;}
/tlb1=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)
{
/tprintf("out of memory");
/treturn;
}
while(s<n)
{
compCount++;
Merge((*L).key,temp,s,n);
/ts*=2;
Merge(temp,(*L).key,s,n);
/ts*=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("MERGESORT COST TIME :%f SECONDS.",*timemerge);
printf("Compare %d times.Shfit %d times.",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:
/tmenu(&comd);
/tswitch (comd)
/t{
/t case 1:
/t/tcreate(&L);
/t/tLOCK3=1;
/t/tbreak;
/t case 2:
/t/timport(&L);
/t/tLOCK3=1;
/t/tgoto start;
/t case 3:
/t/tif(LOCK3==0) goto start;
/t/tmenusort(&comd);
/t/tLOCK4=1;
/t/tLOCK5=1;
/t/tswitch (comd)
/t/t{
/t/t case 1:
/t/t LOCK41=1;
/t/t shell(L,&LS,×hell);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 2:
/t/t LOCK42=1;
/t/t quick(L,&LQ,&timequick);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 3:
/t/t LOCK43=1;
/t/t heap(L,&LH,&timeheap);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 4:
/t/t LOCK44=1;
/t/t domerge(L,&LM,&timemerge);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 5:
/t/t LOCK41=1;
/t/t LOCK42=1;
/t/t LOCK43=1;
/t/t LOCK44=1;
/t/t shell(L,&LS,×hell);
/t/t quick(L,&LQ,&timequick);
/t/t heap(L,&LH,&timeheap);
/t/t domerge(L,&LM,&timemerge);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 6:
/t/t goto start;
/t/t}
/t case 4:
/t/tif(LOCK4==0) goto start;
/t/tmenushow(&comd);
/t/tswitch(comd)
/t/t{
/t/t case 1:
/t/t if(LOCK41==0) goto start;
/t/t for (r=1;r<=LS.length;r++)
/t/t/t printf("%d",LS.key[r]);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 2:
/t/t if(LOCK42==0) goto start;
/t/t for (r=1;r<=LQ.length;r++)
/t/t/t printf("%d",LQ.key[r]);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 3:
/t/t if(LOCK43==0) goto start;
/t/t for (r=1;r<=LH.length;r++)
/t/t/t printf("%d",LH.key[r]);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 4:
/t/t if(LOCK44==0) goto start;
/t/t for (r=1;r<=LM.length;r++)
/t/t/t printf("%d",LM.key[r]);
/t/t printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
/t/t getch();
/t/t goto start;
/t/t case 6:
/t/t goto start;
/t/t}
/t case 5:
/t/tif(LOCK5==0) goto start;
/t/tmenusave(&comd);
/t/tswitch (comd)
/t/t{
/t/t
/t/t case 1:
/t/t/tif(LOCK41==0) goto start;
/t/t/tsave(LS);
/t/t/tbreak;
/t/t case 2:
/t/t/tif(LOCK42==0) goto start;
/t/t/tsave(LQ);
/t/t/tbreak;
/t/t case 3:
/t/t/tif(LOCK43==0) goto start;
/t/t/tsave(LH);
/t/t/tbreak;
/t/t case 4:
/t/t/tif(LOCK44==0) goto start;
/t/t/tsave(LM);
/t/t/tbreak;
/t/t case 6:
/t/t/tbreak;
/t/t/t
/t/t}
/t/tbreak;
/t case 6:
/t/texit(0);
/t}
}
}
