数据结构C实现排序：直接插入、归并和快速排序(递增)学号

1、实验课题：【用C描述课本的同学】有以下结构体构成的数组：struct StudentInfo char ID10;char * name;float score;StuInfo12="0800301105", "JACK", 95,"0800201505", "LUN", 85,"0400820115", "MARY", 75.5,"0400850122", "KATE", 78.9,"0500201011", &q

2、uot;LILI", 88,"0800401105", "JACK", 96,"0600830105", "JAN", 98.4,"0952520012", "SAM", 75,"9721000045", "OSCAR", 64,"0700301105", "JACK", 97,"0458003312", "ZOE", 68.9,"040

3、0830211", "BOBI", 87.6 ; 1 使用直接插入的排序方法按照学号的顺序对以上数组进行排序（递增）；2 分别用归并排序和快速排序按照姓名的顺序对以上数组进行排序（递增），有3人的名字是"JACK"，注意观察排序是否稳定。程序代码:第一种：#include #include #include #include #define Cutoff (3struct StudentInfo char ID10;char * name;double score;StuInfo12="0800301105", "

4、JACK", 95,"0800201505", "LUN", 85,"0400820115", "MARY", 75.5,"0400850122", "KATE", 78.9,"0500201011", "LILI", 88,"0800401105", "JACK", 96,"0600830105", "JAN", 98.4,"09525

5、20012", "SAM", 75,"0721000045", "OSCAR", 64,"0700301105", "JACK", 97,"0458003312", "ZOE", 68.9,"0400830211", "BOBI", 87.6 ,; void InsertionSort(struct StudentInfo A,int Nint j,p;struct StudentInfo Tmp;for(

6、p=1;p Tmp = Ap;for(j=p; j>0&&strcmp(Aj-1.ID,Tmp.ID>0 ; j-Aj=Aj-1;Aj=Tmp;void InsertionSort1(struct StudentInfo A,int Nint j,p;struct StudentInfo Tmp;for(p=1;p Tmp = Ap;for(j=p; j>0&&strcmp(A,T>0 ; j-Aj=Aj-1;Aj=Tmp;void Merge(struct StudentInfo A,struct Stud

7、entInfo TmpArray,int Lpos,int Rpos,int RightEndint i,LeftEnd,NumElements,TmpPos;LeftEnd=Rpos-1;TmpPos=Lpos;NumElements=RightEnd-Lpos+1;while(Lpos<=LeftEnd && Rpos<=RightEndif(strcmp(AL,AR<=0TmpArrayTmpPos+=ALpos+;elseTmpArrayTmpPos+=ARpos+;while(Lpos<=LeftEndTmpAr

8、rayTmpPos+=ALpos+;while(Rpos<=RightEndTmpArrayTmpPos+=ARpos+;for(i=0;i ARightEnd=TmpArrayRightEnd;void MSort(struct StudentInfo A,struct StudentInfo TmpArray,int Left,int Rightint Center;if(Left Center=(Left+Right/2;MSort(A,TmpArray,Left,Center;MSort(A,TmpArray,Center+1,Right;Merge(A,TmpArray,Lef

9、t,Center+1,Right;void Mergesort(struct StudentInfo A,int Nstruct StudentInfo *TmpArray;TmpArray=malloc(N*sizeof(struct StudentInfo;if(TmpArray !=NULLMSort(A,TmpArray,0,N-1;free(TmpArray;elseprintf("No space for tmp array!"void Swap(struct StudentInfo A,struct StudentInfo Bstruct StudentInf

10、o *Tmp;Tmp=A;A=B;B=Tmp;struct StudentInfo Median3(struct StudentInfo A,int Left,int Rightstruct StudentInfo Tmp;int Center=(Left+Right/2;if(strcmp(AL,AC>0Swap(&ALeft,&ACenter;if(strcmp(AL,AR>0Swap(&ALeft,&ARight;if(strcmp(AC,ARight.n

11、ame>0Swap(&ACenter,&ARight;Swap(&ACenter,&ARight-1;return ARight-1;void Qsort(struct StudentInfo A,int Left,int Rightint i,j;struct StudentInfo Pivot,Tmp;if(Left+Cutoff<=RightPivot=Median3(A,Left,Right;i=Left;j=Right-1;for(;while(strcmp(A+,P<0while(strcmp(A-j.

12、name,P>0if(i Swap(&Ai,&Aj;Tmp=Ai;Ai=Aj; Aj=Tmp;elsebreak; Cu + FeQsort(A,Left,i-1;Qsort(A,i+1,Right;（3） InsertionSort1(A+Left,Right-Left+1;void Quicksort(struct StudentInfo A,int NQsort(A,0,N-1;=CO2-void main(int i=0;InsertionSort(StuInfo,12;for(i=0;i<12;i+（4）适量Ba（NO3）2 溶液 Ba2

13、+SO=BaSO4三、推断题（10分）24、（1）(4分 Mergesort(StuInfo,12;for(i=0;i<12;i+printf("%s,%s,%0.1fn",StuInfoi.ID,StuI,StuInfoi.score;Na 2 O 2 for(i=0;i<12;i+ printf("%s,%s,%0.1fn",StuInfoi.ID,StuI,StuInfoi.score;- "0800301105","JACK",95, ）（6分）"0

14、500201011","LILI",88,"0800401105","JACK",96,"0600830105","JAN",98.4,"0952520012","SAM",75,"9721000045","OSCAR",64,"0700301105","JACK",97,"0458003312","ZOE",68.9,&quo

15、t;0400830211","BOBI",87.6;void InsertionSort(ElementType A,int Nint j,P;ElementType Tmp;for(P=1;P Tmp=AP;for(j=P;j>0&&strcmp(Aj-1.ID,Tmp.ID>0;j-Aj=Aj-1;Aj=Tmp;void InsertionSort2(ElementType A,int Nint j,P;ElementType Tmp;for(P=1;P Tmp=AP;for(j=P;j>0&&strcmp(A

16、,T>0;j-Aj=Aj-1;Aj=Tmp;void Merge (ElementType A,ElementType TmpArray,int Lpos,int Rpos,int RightEndint i,LeftEnd,NumElements,Tmpos;LeftEnd=Rpos-1;Tmpos=Lpos;NumElements=RightEnd-Lpos+1;while(Lpos<=LeftEnd&&Rpos<=RightEndif(strcmp(AL,AR<=0TmpArrayTmp

17、os+=ALpos+;elseTmpArrayTmpos+=ARpos+;while(Lpos<=LeftEndTmpArrayTmpos+=ALpos+;while(Rpos<=RightEndTmpArrayTmpos+=ARpos+;for(i=0;i ARightEnd=TmpArrayRightEnd;void MSort(ElementType A,ElementType TmpArray,int Left,int Rightint center;if(Left center=(Left+Right/2;MSort(A,TmpArray,Left,center;MSor

18、t(A,TmpArray,center+1,Right;Merge(A,TmpArray,Left,center+1,Right;void Mergsort(ElementType A,int NElementType *TmpArray;TmpArray=(ElementType*malloc(N*sizeof(ElementType;if(TmpArray!=NULLMSort(A,TmpArray,0,N-1;free(TmpArray;elseprintf("No space for tmp array!"void Swap(ElementType *A,Eleme

19、ntType *BElementType XX;XX=*A;*A=*B;*B=XX;ElementType Median3(ElementType A,int Left,int Rightint Center=(Left+Right/2;if(strcmp(AL,AC>0Swap(&ALeft,&ACenter;if(strcmp(AL,AR>0Swap(&ALeft,&ARight;if(strcmp(AC,AR>0Swap(&ACenter,&ARight;Swap(&ACenter,&ARight-1;return ARight-1;#define Cutoff 3void Qsort(ElementType A,int Left,int Rightint i,j;ElementType Pivot;if(Left+Cutoff<=RightPivot=Median3(A,Left,R