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

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

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

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

4、name;double score;StuInfo12="0800301105", "JACK", 95,"0800201505", "LUN", 85,"0400820115", "MARY", 75.5,"0400850122", "KATE", 78.9,"0500201011", "LILI", 88,"0800401105", "JACK", 96

5、,"0600830105", "JAN", 98.4,"0952520012", "SAM", 75,"0721000045", "OSCAR", 64,"0700301105", "JACK", 97,"0458003312", "ZOE", 68.9,"0400830211", "BOBI", 87.6 ,; void InsertionSort(str

6、uct StudentInfo A,int N)int j,p;struct StudentInfo Tmp; for(p=1;p<N;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 N)int j,p;struct StudentInfo Tmp; for(p=1;p<N;p+)Tmp = Ap;for(j=p; j>0&&strcmp(Aj-1.n

7、ame,T)>0 ; j-)Aj=Aj-1;Aj=Tmp;void Merge(struct StudentInfo A,struct StudentInfo TmpArray,int Lpos,int Rpos,int RightEnd)int i,LeftEnd,NumElements,TmpPos;LeftEnd=Rpos-1;TmpPos=Lpos;NumElements=RightEnd-Lpos+1;while(Lpos<=LeftEnd && Rpos<=RightEnd)if(strcmp(AL,ARpos.nam

8、e)<=0)TmpArrayTmpPos+=ALpos+;elseTmpArrayTmpPos+=ARpos+;while(Lpos<=LeftEnd)TmpArrayTmpPos+=ALpos+;while(Rpos<=RightEnd)TmpArrayTmpPos+=ARpos+; for(i=0;i<NumElements;i+,RightEnd-)ARightEnd=TmpArrayRightEnd;void MSort(struct StudentInfo A,struct StudentInfo TmpArray,int Left,int Right)int

9、 Center;if(Left<Right)Center=(Left+Right)/2;MSort(A,TmpArray,Left,Center);MSort(A,TmpArray,Center+1,Right); Merge(A,TmpArray,Left,Center+1,Right);void Mergesort(struct StudentInfo A,int N) struct StudentInfo *TmpArray; TmpArray=malloc(N*sizeof(struct StudentInfo);if(TmpArray !=NULL)MSort(A,TmpArr

10、ay,0,N-1);free(TmpArray);elseprintf("No space for tmp array!");void Swap(struct StudentInfo A,struct StudentInfo B) struct StudentInfo *Tmp;Tmp=A;A=B;B=Tmp;struct StudentInfo Median3(struct StudentInfo A,int Left,int Right) struct StudentInfo Tmp; int Center=(Left+Right)/2; if(strcmp(ALeft

11、.name,AC)>0) Swap(&ALeft,&ACenter); if(strcmp(AL,AR)>0) Swap(&ALeft,&ARight); if(strcmp(AC,AR)>0) Swap(&ACenter,&ARight); Swap(&ACenter,&ARight-1); return ARight-1;void Qsort(struct StudentInfo A,int Left,int Righ

12、t)int i,j; struct StudentInfo Pivot,Tmp;if(Left+Cutoff<=Right)Pivot=Median3(A,Left,Right);i=Left;j=Right-1;for(;)while(strcmp(A+,P)<0)while(strcmp(A-,P)>0)if(i<j) Swap(&Ai,&Aj); Tmp=Ai;Ai=Aj;Aj=Tmp;elsebreak;Swap(&Ai,&ARight-1); Qsort(A,Left,

13、i-1);Qsort(A,i+1,Right); InsertionSort1(A+Left,Right-Left+1);void Quicksort(struct StudentInfo A,int N)Qsort(A,0,N-1);第二种：void main()int i=0;InsertionSort(StuInfo,12); for(i=0;i<12;i+)printf("%s,%s,%0.1fn",StuInfoi.ID,StuI,StuInfoi.score);printf("nn"); Mergesort(StuIn

14、fo,12);for(i=0;i<12;i+)printf("%s,%s,%0.1fn",StuInfoi.ID,StuI,StuInfoi.score);printf("nn"); Quicksort(StuInfo,12);for(i=0;i<12;i+)printf("%s,%s,%0.1fn",StuInfoi.ID,StuI,StuInfoi.score);#include<stdio.h>#include<stdlib.h>#include<st

15、ring.h>typedef struct StudentInfo ElementType;struct StudentInfochar ID11;char *name;double score;StuInfo12="0800301105","JACK",95,"0800201505","LUN",85,"0400820115","MARY",75.05,"0400850122","KATE",78.9,"0500201

16、011","LILI",88,"0800401105","JACK",96,"0600830105","JAN",98.4,"0952520012","SAM",75,"9721000045","OSCAR",64,"0700301105","JACK",97,"0458003312","ZOE",68.9,"0400

17、830211","BOBI",87.6;void InsertionSort(ElementType A,int N)int j,P;ElementType Tmp;for(P=1;P<N;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 N)int j,P;ElementType Tmp;for(P=1;P<N;P+)Tmp=AP;for(j=P;j>0&

18、;&strcmp(A,T)>0;j-)Aj=Aj-1;Aj=Tmp;void Merge (ElementType A,ElementType TmpArray,int Lpos,int Rpos,int RightEnd)int i,LeftEnd,NumElements,Tmpos;LeftEnd=Rpos-1;Tmpos=Lpos;NumElements=RightEnd-Lpos+1;while(Lpos<=LeftEnd&&Rpos<=RightEnd)if(strcmp(AL,ARpos.nam

19、e)<=0)TmpArrayTmpos+=ALpos+;elseTmpArrayTmpos+=ARpos+;while(Lpos<=LeftEnd)TmpArrayTmpos+=ALpos+;while(Rpos<=RightEnd)TmpArrayTmpos+=ARpos+;for(i=0;i<NumElements;i+,RightEnd-)ARightEnd=TmpArrayRightEnd;void MSort(ElementType A,ElementType TmpArray,int Left,int Right)int center;if(Left<

20、Right)center=(Left+Right)/2;MSort(A,TmpArray,Left,center);MSort(A,TmpArray,center+1,Right);Merge(A,TmpArray,Left,center+1,Right);void Mergsort(ElementType A,int N)ElementType *TmpArray;TmpArray=(ElementType*)malloc(N*sizeof(ElementType);if(TmpArray!=NULL)MSort(A,TmpArray,0,N-1);free(TmpArray);elsepr

21、intf("No space for tmp array!");void Swap(ElementType *A,ElementType *B)ElementType XX;XX=*A;*A=*B;*B=XX;ElementType Median3(ElementType A,int Left,int Right)int Center=(Left+Right)/2;if(strcmp(AL,AC)>0)Swap(&ALeft,&ACenter);if(strcmp(AL,AR)>0)Swap(&ALeft,&ARight);if(strcmp(AC,AR)>0)Swap(&ACenter,&ARight);Swap(&ACenter,&ARight-1);return ARight-1;#define Cutoff 3void Qsort(ElementType A,int Left,int Right)int i,j;ElementType Pivot;if(Left+Cutof