sort.cpp

数据结构清华大学出版社严蔚敏,吴为民编著的课后习题实验源代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#define MAXSIZE 120
#define FALSE  0
#define TRUE  1
typedef struct{
   int r[MAXSIZE+1];
   int Length;
   }SqList;
int CompareCount,MoveCount;
void SortInit(SqList *L)
{ int i,j,k,temp;
  L->r[1]=random(1000);
  for(i=2;i<=MAXSIZE;i++)
   { do{
	temp=random(1000);
	for(j=1;j<i;j++)
	  if(temp==L->r[j]) break;
	}while(j<i);
     L->r[i]=temp;
     }
  L->Length=MAXSIZE;
  }
void DataCopy(SqList L,SqList *L1)
{ int i;
  L1->Length=L.Length;
  for(i=1;i<=L.Length;i++)
    L1->r[i]=L.r[i];
  }
void InsertSort(SqList *L)
 { int i,j,temp;
   CompareCount=0;
   MoveCount=0;
   for(i=2;i<=L->Length;i++)
   { CompareCount++;
     if(L->r[i]<L->r[i-1])
       { L->r[0]=L->r[i];
	 MoveCount++;
	 for(j=i-1;L->r[0]<L->r[j];j--)
	  { L->r[j+1]=L->r[j];
	    CompareCount++;
	    MoveCount++;
	    }
	 L->r[j+1]=L->r[0];
	 MoveCount++;
	 }
     }
    }
void ShellInsert(SqList *L,int dk)
 { int i,j,temp;
   
   for(i=dk+1;i<=L->Length;i++)
   { CompareCount++;
     if(L->r[i]<L->r[i-dk])
       { L->r[0]=L->r[i];
	 MoveCount++;
	 for(j=i-dk;j>0&&L->r[0]<L->r[j];j-=dk)
	 { CompareCount++;
	   L->r[j+dk]=L->r[j];
	   MoveCount++;
	   }
	 L->r[j+dk]=L->r[0];
	 MoveCount++;
	 }
      }
    }
void ShellSort(SqList *L)
 { int t,i,j,k,dlta[MAXSIZE/3]={0};
   CompareCount=0;
   MoveCount=0;
   k=0;
   dlta[0]=L->Length/2;
   while(dlta[k]>1)
    { k++;
      dlta[k]=(dlta[k-1]+1)/2;
      }
   t=k+1;
   for(k=0;k<t;k++)
     ShellInsert(L,dlta[k]);
   }
void BubbleSort(SqList *L)
 { int i,j,flag;
   CompareCount=0;
   MoveCount=0;
   for(i=L->Length;i>1; --i)
     { flag=FALSE;
       for(j=1;j<i;++j)
       { CompareCount++;
	 if(L->r[j]>L->r[j+1])
	   { L->r[0]=L->r[j];
	     L->r[j]=L->r[j+1];
	     L->r[j+1]=L->r[0];
	     flag=TRUE;
	     MoveCount+=3;
	     }
          }
       if (!flag) break;
       }
   }
int Partition(SqList *L,int low,int high)
{ int pivot;
  pivot=L->r[low];
  MoveCount++;
  while(low<high)
  { while(low<high&&L->r[high]>=pivot)
     { --high;
       CompareCount++;
       }
    L->r[low]=L->r[high];
    MoveCount++;
    while(low<high&&L->r[low]<=pivot)
      { ++low;
	CompareCount++;
	}
    L->r[high]=L->r[low];
    MoveCount++;
    }
  L->r[low]=pivot;
  MoveCount++;
  return(low);
  }
void QickSort(SqList *L,int low,int high)
{ int pivotloc;
  if(low<high)
   { pivotloc=Partition(L,low,high);
     QickSort(L,low,pivotloc-1);
     QickSort(L,pivotloc+1,high);
     }
  }
void SelectSort(SqList *L)
{ int i,j,k;
  CompareCount=0;
  MoveCount=0;
  for(i=1;i<L->Length;i++)
   { k=i;
     for(j=i+1;j<=L->Length;j++)
     { CompareCount++;
       if(L->r[j]<L->r[k]) k=j;
       }
     if(k!=i)
       { L->r[0]=L->r[i];
	 L->r[i]=L->r[k];
	 L->r[k]=L->r[0];
	 MoveCount+=3;
	 }
     }
 }
void HeapAdjust(SqList *L,int s,int m)
{ int rc,j;
  rc=L->r[s];
  MoveCount++;
  for(j=2*s;j<=m;j=j*2)
   { if(j<m&&(L->r[j]<L->r[j+1]))
      { ++j;
	CompareCount++;
	}
     CompareCount++;
     if(!(rc<L->r[j])) break;
     L->r[s]=L->r[j];
     MoveCount++;
     s=j;
     }
   L->r[s]=rc;
   MoveCount++;
  }
void HeapSort(SqList *L)
{ int i;
  CompareCount=0;
  MoveCount=0;
  for(i=L->Length/2;i>0;--i)
    HeapAdjust(L,i,L->Length);
  for(i=L->Length;i>1;--i)
   { L->r[0]=L->r[1];
     L->r[1]=L->r[i];
     L->r[i]=L->r[0];
     MoveCount+=3;
     HeapAdjust(L,1,i-1);
     }
  }
void OutputSortData(SqList L)
{ int i;
  for(i=1;i<=MAXSIZE;i++)
   { if((i-1)%10==0) printf("\n");
     printf("%6d",L.r[i]);
     }
   getchar();
   }
char nemu()
{
    int mun;
    printf("\n    *****************sort ******************\n");
    printf("    *%8c1---Random Data sort%11c\n",' ','*');
    printf("    *%8c2---Increasing Data sort%7c\n",' ','*');
    printf("    *%8c3---Decreasing Data sort%7c\n",' ','*');
    printf("    *%8c4---Time Complexity Output%5c\n",' ','*');
    printf("    *%8c5---End%24c\n",' ','*');
    printf("    ****************************************\n");
    printf("%15cSelcet 1,2,3,4: ",' ');
    do{
	mun=getch()-48;
	}while(mun<0 || mun>4);
    printf("\n");
    return(mun);
}
void sort(SqList L,SqList *L1,int a[][6],int No)
{  //insert
   DataCopy(L,L1);
   InsertSort(L1);
   a[1][No]=CompareCount;
   a[1][No+1]=MoveCount;
   OutputSortData(*L1);
   //shell
   DataCopy(L,L1);
   ShellSort(L1);
   a[2][No]=CompareCount;
   a[2][No+1]=MoveCount;
   OutputSortData(*L1);
   //Bubble
   DataCopy(L,L1);
   BubbleSort(L1);
   a[3][No]=CompareCount;
   a[3][No+1]=MoveCount;
   OutputSortData(*L1);
   //quik
   DataCopy(L,L1);
   CompareCount=0;
   MoveCount=0;
   QickSort(L1,1,L1->Length);
   a[4][No]=CompareCount;
   a[4][No+1]=MoveCount;
   OutputSortData(*L1);
   //select
   DataCopy(L,L1);
   SelectSort(L1);
   a[5][No]=CompareCount;
   a[5][No+1]=MoveCount;
   OutputSortData(*L1);
   //heap
   DataCopy(L,L1);
   HeapSort(L1);
   a[6][No]=CompareCount;
   a[6][No+1]=MoveCount;
   OutputSortData(*L1);
  }
void CompareShift(char SortName[][15],int a[][6])
 { int i,j;
   printf("%4cSortName     Random           Increase        Decrease\n",' ');
   for(i=1;i<=6;i++)
     { printf("%4c%6s%5c",' ',SortName[i],' ');
       for(j=0;j<6;j++) printf("%8d",a[i][j]);
       printf("\n");
       }
   getchar();
   return;
  }
void main()
{ int i,j,flag=0,a[7][6]={0,0,0};
  FILE *fp;
  char SortName[][15]={"","Insert","Shell","Buble","Quick","Select","Heap"};
  SqList L,L1,L2,L3;
  SortInit(&L);
  while(1)
    { switch(nemu())
	{
	    case 1:
		flag=1;
                sort(L,&L1,a,0);
		break;
	    case 2:
		if(flag==0)
		  { printf("Please select 1\n");
		    getchar();
		    break;
		    }
		sort(L1,&L2,a,2);
		break;
	    case 3:
		if(flag==0)
		  { printf("Please select 1\n");
		    getchar();
		    break;
		    }
		L3.Length=L1.Length;
		for(i=1,j=L1.Length;i<=L1.Length;i++,j--)
		  L3.r[j]=L1.r[i];
                sort(L3,&L2,a,4);
		break;
	    case 4:
	       if(flag==0) return;
	       CompareShift(SortName,a);
            case 5:
	       return;
	}
    }
}