当前位置:首页 >> 编程开发 >> Visual C++ >> 内容

排序算法比较程序

时间:2008/4/4 作者:平凡之路 来源:xuhantao.com 浏览:

功能要求如下:

排序算法比较: 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,&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);
    }
  
  }  
  
}

  • 上一篇:TList
  • 下一篇:C++的算符重载
  • 相关文章
    • 没有相关文章
    共有评论 0相关评论
    发表我的评论
    • 大名:
    • 内容:
  • 徐汉涛(www.xuhantao.com) © 2024 版权所有 All Rights Reserved.
  • 部分内容来自网络,如有侵权请联系站长尽快处理 站长QQ:965898558(广告及站内业务受理) 网站备案号:蒙ICP备15000590号-1