直接插入排序 快速排序 大根堆排序 归并排序

1、#include #include #include #include #define MAXSIZE 100/*定义和初始化顺序表*/typedef int DataType;typedef struct node DataType dataMAXSIZE;int length;SeqList,*PseqList;/定义一个顺序表。PseqList Init_SeqList(voidPseqList PL;PL=(PseqListmalloc(sizeof(SeqList;if(PLPL->length=0;return(PL;/顺序表的初始化./*直接插入排序*/void Strai

2、ghtInsertSort(SeqList *sint i,j;for(i=2;i length;i+ s->data0=s->datai;for(j=i-1;s->data0 dataj;j- s->dataj+1=s->dataj;s->dataj+1=s->data0;/*快速排序*/int QuickSort1(SeqList *s,int low,int highs->data0=s->datalow;while(low while(low datahigh>=s->data0 high-;s->datalow=

3、s->datahigh;while(low datalow<=s->data0 low+;s->datahigh=s->datalow;s->datalow=s->data0;return low;void QuickSort(PseqList s,int low,int highint m;if(low m=QuickSort1(s,low,high;QuickSort(s,low,m-1;QuickSort(s,m+1,high;/*大根堆排序*/void HeapAdjust(SeqList *s,int n,int mint i,j;s->

4、;data0=s->datan;i=n;for(j=2*i;j<=m;j=j*2if(j dataj dataj+1 j+;if(s->data0>s->dataj break;s->datai=s->dataj;i=j;s->datai=s->data0;void HeapSort(SeqList *sint i;for(i=s->length/2;i>0;i-HeapAdjust(s,i,s->length-1;for(i=s->length-1;i>1;i-s->data0=s->data1;

5、s->data1=s->datai;s->datai=s->data0;HeapAdjust(s,1,i-1;/*归并排序*/ void Merge(DataType r,DataType rf,int u,int v,int tint i,j,k;for(i=u,j=v+1,k=u;i<=v&&j<=t;k+if(ri<=rjrfk=ri;i+;else rfk=rj;j+;while(i<=v rfk+=ri+;while(j<=t rfk+=rj+;void MSort(DataType p,DataType p1,i

6、nt n,int tint m;DataType p2MAXSIZE+1;if(n=tp1n=pn;else m=(n+t/2;MSort(p,p2,n,m;MSort(p,p2,m+1,t;Merge(p2,p1,n,m,t;void MergeSort(PseqList sMSort(s->data,s->data,1,s->length-1;/*主函数*/void main(PseqList p;int i,n=0;srand(unsignedtime(NULL;p=Init_SeqList(;for(i=1;i<=20;i+ p->datai=rand(%

7、20+1;p->length=i;printf("输 出 原 序 列：n"for(i=1;i length;i+ printf("%3d",p->datai; while(n=0|n=1|n=2|n=3|n=4printf("n请选择：1.直接插入排序;2.快速排序;3.大根堆排序;4.归并排序;其它退出n"n=0;scanf("%d",&n;switch(ncase 1:StraightInsertSort(p;printf("输出直接插入排序后序列：n"break;case 2:QuickSort(p,1,p->length-1;printf("输出快速排序序列：n"break;case 3:HeapSort(p;printf("输出大根堆排序序列：n"break;case 4:MergeSort(p; printf("输出归并排序序列：n"break;