《排序(希尔,快速,堆排序等)》由会员分享，可在线阅读，更多相关《排序(希尔,快速,堆排序等)（13页珍藏版）》请在金锄头文库上搜索。
1、#include“stdio.h“ #include“math.h“ #include“stdlib.h“ #include“malloc.h“ #define Maxsize 10000000 #define N 20 #define EQ(a,b) (a)=(b) #define LT(a,b) (a)length=0;if(fp=fopen(filename,“r“)=NULL)/文件不存在时终止程序 printf(“cannot open filen“);exit(0); for(i=1;iri.key),if(L-ri.keylength+;/记录读入的数据长度 fclose(fp)
2、;return(L); void Print2(qSqList L)/将序列输出到指定的文件中 long i; FILE *fp; char filenameN;printf(“nt 请输入存储文件名：“);scanf(“%s“,filename);/输入将要储存的文件名fp=fopen(filename,“w“);for(i=1;ilength;i+)/将链表中数据逐一写入文件中 fprintf(fp,“%d (%d)n“,L-ri.key,L-ri.num); fclose(fp); void Print(qSqList L)/打印数据个数以及排序过程中的比较次数和移动次数 printf(
3、“nt 数据个数:%ld“,L-length);printf(“nt 比较次数:%ld“,comparetimes);printf(“nt 移动次数:%ld“,shifttimes); struct node Min1(struct node a,struct node b)/比较两接点关键字的大小 struct node temp;if(a.keyb.key) temp=b;elsetemp=a;comparetimes+;return(temp); qSqList shellinsert(qSqList L,int dk)/对顺序表以 dk 为增量作直接插入排序 int i,j; for(
4、i=dk+1;ilength;i+) if(LT(L-ri.key,L-ri-dk.key)/将 L-ri插入到有序增量子表 L-r0=L-ri;/将 L-ri暂时存储在 L-r0shifttimes+;for(j=i-dk;j0j-=dk)/记录后移，查找插入位置 L-rj+dk=L-rj;comparetimes+;shifttimes+; if(j0) comparetimes+;L-rj+dk=L-r0;/插入shifttimes+; comparetimes+; / Print(L); return(L); qSqList shell(qSqList L)/希尔排序 int i,t=
5、0;int k;for(t=0;LQ(pow(2,t),(L-length+1);t+);t=t-1;/ printf(“%d“,t);for(i=1;irlow.high的记录，使 枢轴记录到位，并返回其所在位置 int pivotkey;pivotkey=L-rlow.key;/用序列的第一个记录作枢轴记录while(lowrhigh.key=pivotkey)/将比枢轴记录小的记录交换到低端 comparetimes+;high-; comparetimes+;L-r0=L-rlow;shifttimes+;L-rlow=L-rhigh;shifttimes+;L-rhigh=L-r0;
6、shifttimes+;while(lowrlow.keyr0=L-rlow;shifttimes+;L-rlow=L-rhigh;shifttimes+;L-rhigh=L-r0;shifttimes+; return(low);/返回枢轴所在位置 qSqList Quick2(qSqList L,long low,long high)/对顺序表 L 中的子序列 L.rlow.high作快速排序 long pivot;if(lowlength;/将最后一个数据所在位置定义为高位L=Quick2(L,low,high);/对顺序表作快速排序Print(L);Print2(L);return(L
7、); void TourSort(SqList *L,long n)/锦标赛排序 qSqList Lp;long i=0,t=1,k=1,w;while(tlength=t-1;for(i=t-1;i=t/2;i-) if(kn) Lp-ri.key=MAXNUM;else Lp-ri=L-rk; shifttimes+;k+; i=t-1;while(i!=1) Lp-ri/2=Min1(Lp-ri,Lp-ri-1);i-=2;comparetimes+;shifttimes+; for(i=1;iri=Lp-r1;shifttimes+;w=1;while(wr2*w.key=Lp-rw.
8、key) w*=2;elsew=2*w+1; Lp-rw.key=MAXNUM;/将其赋为最大值shifttimes+;if(w%2) Lp-rw/2=Lp-rw-1;elseLp-rw/2=Lp-rw+1;shifttimes+;while(w!=1) if(w%2)Lp-rw/2=Min1(Lp-rw,Lp-rw-1);elseLp-rw/2=Min1(Lp-rw,Lp-rw+1);comparetimes+;shifttimes+;w/=2; Print(L);Print2(L); void Heapadjust(qSqList L,long s,long m)/调整 L-s的关键字，使
9、 L-rs.m成为一个大顶堆 long j;struct node rc;rc=L-rs;for(j=2*s;jrj.key,L-rj+1.key)/j 为 key 较大的记录的下标 j+;comparetimes+; if(!LT(rc.key,L-rj.key) comparetimes+;break; L-rs=L-rj;/rc 插入位置 sshifttimes+;s=j; L-rs=rc;/插入shifttimes+; qSqList Heap(qSqList L)/堆排序 long i;for(i=L-length/2;i0;-i)/把 L 建成大顶堆Heapadjust(L,i,L
10、-length);for(i=L-length;i1;-i)/将堆顶记录和当前未经排序子序列中最后一个记录交换 L-r0=L-r1;L-r1=L-ri;L-ri=L-r0;shifttimes=shifttimes+3;Heapadjust(L,1,i-1);/将 L 重新调整为大顶堆 Print(L);Print2(L);return(L); void Merge(qSqList L,int low,int m,int high)/将两个有序表 Rlow.mhe Rm+1.high归并为 一个有序表 Rlow,high int i=low,j=m+1,k=0;/k 是 temp 的下标，i,
11、j 分别为第 1，2 段的下标struct node *temp;temp=(struct node*)malloc(high-low+1)*sizeof(struct node);/用于临时保存有序序列while(irj.key,L-ri.key)/将第 1 段中的记录放入 temp 中 tempk=L-rj;j+;k+; else/将第 2 段中的记录放入 temp 中 tempk=L-ri;k+;i+; while(iri;k+;i+; while(jrj;k+;j+; for(k=0,i=low;iri=tempk; void MSort(qSqList L,int low,int h
12、igh)/二路归并排序 int m;if (lowlength);Print2(L); void Radixsort(qSqList L)/基数排序 int g,i,j,k,d=2;struct node2 *p,*s,*t,*head10,*tail10;/定义各链队的首尾指针for(i=1;ilength;i+) /建立链表 s = (struct node2*)malloc(sizeof(struct node2);s-r.key = L-ri.key;s-r.num= L-ri.num;if(i=1) t = s;p = s;g+; else t-next = s;t = s;g+;
13、t-next = NULL; d=1;for(i=1;ir.key/d;k = k%10;if(headk=NULL)/进行分配 headk=p;tailk=p; else tailk-next=p;tailk=p; p = p-next;/取下一个待排序的元素 p=NULL;for(j=0;jnext=headj;t = tailj; t-next=NULL;/最后一个结点的 next 置为空d=d*10;i=1;while(p!=NULL) L-ri = p-r;i+;p=p-next; Print2(L); char chmenu()/对排序方法进行选择 char ch;printf(“
14、nt 请选择排序方法:“nt*“nt1.Shell 排序“nt2.Quick 排序“nt3.锦标赛排序“nt4.堆排序“nt5.归并排序“nt6.基排序“nt7.结束“nt*“);do printf(“ntplease choose (1-7):“); getchar();ch=getchar(); while(!(ch0 break;case4: shifttimes=comparetimes=0; Heap(L); break;case5: shifttimes=comparetimes=0; Merging(L); break;case6: shifttimes=comparetimes=0; Radixsort(L); break; printf(“nt*“nt1.继续读入文件“nt0.结束“nt*“);doprintf(“ntplease choose (0-1):“);getchar();scanf(“%d“, while(!(a=1|a=0);
