排序算法比较程序

功能要求如下：

排序算法比较: 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");
    for (i=0;i<6;i++) printf("%s",menu[i]);
    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",
                            "4 MERGE SORT","5 ALL SORT"};
    
    clrscr();
    printf("SORT");
    for(i=0;i<5;i++) printf("%s",menusort[i]);
    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",
                            "3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
    
    clrscr();
    printf("SHOW SORT RESULT");
    for(i=0;i<4;i++) printf("%s",menushow[i]);
    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",
                           "3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
    
    clrscr();
    printf("SAVE:");
    for (i=0;i<4;i++) printf("%s",menusave[i]);
    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++)
    {
        printf("PLEASE INPUT THE %dth DATA:",i);
        scanf("%d",&(*L).key[i]);
    }
    printf("CREATE COMPLETE !");
        
}


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("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[i]);
    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();
        
}


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("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)
    {
        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("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[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("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)
    {
        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("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:
        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(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    getch();
                    goto start;
                 case 2:
                    LOCK42=1;
                    quick(L,&LQ,&timequick);
                    printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    getch();
                    goto start;
                 case 3:
                    LOCK43=1;
                    heap(L,&LH,&timeheap);
                    printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    getch();
                    goto start;
                 case 4:
                    LOCK44=1;
                    domerge(L,&LM,&timemerge);
                    printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    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(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    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(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    getch();
                    goto start;
                 case 2:
                    if(LOCK42==0) goto start;
                    for (r=1;r<=LQ.length;r++)
                         printf("%d",LQ.key[r]);
                    printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    getch();
                    goto start;
                 case 3:
                    if(LOCK43==0) goto start;
                    for (r=1;r<=LH.length;r++)
                         printf("%d",LH.key[r]);
                    printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    getch();
                    goto start;
                 case 4:
                    if(LOCK44==0) goto start;
                    for (r=1;r<=LM.length;r++)
                         printf("%d",LM.key[r]);
                    printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                    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);
        }
    
    }    
    

}