排序算法比较程序

排序算法比较程序2008-04-04功能要求如下：
排序算法比较: 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,&timeshell）;
          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,&timeshell）;
          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）;
    }
  
  }  
  
}