排序(希尔,快速,堆排序等)

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)<(b)#define LQ(a,b) (a)<=(b)#define LEN sizeof(SqList)#define Maxr 10#define MAXNUM 100000000typedef struct

2、 nodeint key; int num;node;typedef struct struct node rMaxsize+1; long length;SqList,*qSqList;typedef struct node2struct node r; struct node2 *next;RecType;long shifttimes;/统计移动次数long comparetimes;/统计比较次数qSqList creat(char filename)/读入文件并且将数据保存FILE *fp;long i;qSqList L;L=(qSqList)malloc(LEN);L->l

3、ength=0;if(fp=fopen(filename,"r")=NULL)/文件不存在时终止程序 printf("cannot open filen"); exit(0);for(i=1;i<Maxsize+1;i+) fscanf(fp,"%ld (%d)",&(L->ri.key),&(L->ri.num); if(L->ri.key<0)break; L->length+;/记录读入的数据长度fclose(fp); return(L);void Print2(qSqList

4、 L)/将序列输出到指定的文件中long i;FILE *fp;char filenameN; printf("nt请输入存储文件名："); scanf("%s",filename);/输入将要储存的文件名 fp=fopen(filename,"w"); for(i=1;i<=L->length;i+)/将链表中数据逐一写入文件中fprintf(fp,"%d (%d)n",L->ri.key,L->ri.num); fclose(fp);void Print(qSqList L)/打印数据个

5、数以及排序过程中的比较次数和移动次数printf("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.key>b.key)temp=b;else temp=a; comparetimes+; return(temp);qSqList s

6、hellinsert(qSqList L,int dk)/对顺序表以dk为增量作直接插入排序int i,j;for(i=dk+1;i<=L->length;i+)if(LT(L->ri.key,L->ri-dk.key)/将L->ri插入到有序增量子表L->r0=L->ri;/将L->ri暂时存储在L->r0 shifttimes+; for(j=i-dk;j>0&&j<(L->r0.key,L->rj.key);j-=dk)/记录后移，查找插入位置L->rj+dk=L->rj; comp

7、aretimes+; shifttimes+;if(j>0)comparetimes+; L->rj+dk=L->r0;/插入 shifttimes+; comparetimes+;/ Print(L); return(L);qSqList shell(qSqList L)/希尔排序int i,t=0; int k; for(t=0;LQ(pow(2,t),(L->length+1);t+); t=t-1; / printf("%d",t); for(i=1;i<=t;+i) k=(int)pow(2,t-i+1)-1;/计算排序增量 L=sh

8、ellinsert(L,k); Print(L); Print2(L); return(L);long Quicksort(qSqList L,long low,long high)/交换顺序表L中子表L->rlow.high的记录，使枢轴记录到位，并返回其所在位置int pivotkey; pivotkey=L->rlow.key;/用序列的第一个记录作枢轴记录 while(low<high)/从表的两端交替地向中间扫描 while(low<high&&L->rhigh.key>=pivotkey)/将比枢轴记录小的记录交换到低端compa

9、retimes+; high-; comparetimes+; L->r0=L->rlow; shifttimes+; L->rlow=L->rhigh; shifttimes+; L->rhigh=L->r0; shifttimes+; while(low<high&&L->rlow.key<=pivotkey)/将比枢轴记录大的记录交换到高端comparetimes+; low+; comparetimes+; L->r0=L->rlow; shifttimes+; L->rlow=L->rhig

10、h; shifttimes+; L->rhigh=L->r0; shifttimes+; return(low);/返回枢轴所在位置qSqList Quick2(qSqList L,long low,long high)/对顺序表L中的子序列L.rlow.high作快速排序long pivot; if(low<high)/序列长度大于1pivot=Quicksort(L,low,high);/将序列一分为二 Quick2(L,low,pivot-1);/对低位子表递归排序 Quick2(L,pivot+1,high);/对高位子表递归排序 return(L);qSqList

11、Quick(qSqList L)/对顺序表作快速排序long low,high; low=1;/将第一个数据所在位置定义为低位 high=L->length;/将最后一个数据所在位置定义为高位 L=Quick2(L,low,high);/对顺序表作快速排序 Print(L); Print2(L); return(L);void TourSort(SqList *L,long n)/锦标赛排序 qSqList Lp; long i=0,t=1,k=1,w; while(t<n)/t表示完全二叉树的结点个数t=(long)pow(2,i); i+; t=2*t; Lp=(qSqList

12、)malloc(sizeof(SqList); Lp->length=t-1; for(i=t-1;i>=t/2;i-)if(k>n)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;i<=n;i+)L->ri=Lp->r1; shifttimes+; w=1; while(w<

13、;t/2)if(Lp->r2*w.key=Lp->rw.key)w*=2; else w=2*w+1; Lp->rw.key=MAXNUM;/将其赋为最大值 shifttimes+; if(w%2)Lp->rw/2=Lp->rw-1; else Lp->rw/2=Lp->rw+1; shifttimes+; while(w!=1) if(w%2) Lp->rw/2=Min1(Lp->rw,Lp->rw-1); else Lp->rw/2=Min1(Lp->rw,Lp->rw+1); comparetimes+; sh

14、ifttimes+; w/=2; Print(L); Print2(L); void Heapadjust(qSqList L,long s,long m)/调整L->s的关键字，使L->rs.m成为一个大顶堆long j; struct node rc; rc=L->rs; for(j=2*s;j<=m;j*=2)/沿key较大的接点向下筛选 if(j<m&&j<(L->rj.key,L->rj+1.key)/j为key较大的记录的下标j+; comparetimes+; if(!LT(rc.key,L->rj.key)

15、comparetimes+; break; L->rs=L->rj;/rc插入位置s shifttimes+; s=j; L->rs=rc;/插入 shifttimes+;qSqList Heap(qSqList L)/堆排序long i;for(i=L->length/2;i>0;-i)/把L建成大顶堆 Heapadjust(L,i,L->length); for(i=L->length;i>1;-i)/将堆顶记录和当前未经排序子序列中最后一个记录交换L->r0=L->r1; L->r1=L->ri; L->ri=

16、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,highint i=low,j=m+1,k=0;/k是temp的下标，i,j分别为第1，2段的下标 struct node *temp; temp=(struct node*)malloc(high-low+1)*sizeof(struct

17、 node);/用于临时保存有序序列 while(i<=m&&j<=high)/在第1段和第2段均未扫描完时循环 if(LT(L->rj.key,L->ri.key)/将第1段中的记录放入temp中 tempk=L->rj; j+; k+; else/将第2段中的记录放入temp中 tempk=L->ri; k+; i+; while(i<=m)/将第1段余下的部分复制到temp tempk=L->ri; k+; i+; while(j<=high)/将第2段余下的部分复制到temp tempk=L->rj; k+;

18、j+; for(k=0,i=low;i<=high;i+,k+)/将temp复制回L中 L->ri=tempk;void MSort(qSqList L,int low,int high)/二路归并排序int m; if (low<high) m=(low+high)/2; MSort(L,low,m); MSort(L,m+1,high); Merge(L,low,m,high);void Merging(qSqList L)/归并排序MSort(L,1,L->length); Print2(L);void Radixsort(qSqList L)/基数排序int g

19、,i,j,k,d=2; struct node2 *p,*s,*t,*head10,*tail10;/定义各链队的首尾指针 for(i=1;i<=L->length;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+; t->next = NULL; d=1; for(i=1;i<6;i

20、+) for(j=0;j<10;j+)headj = tailj = NULL; /初始化各链队首、尾指针 while(p!=NULL)/对于原链表中的每个结点循环 k = p->r.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;j<10;j+)/对每一个链队循环 if(headj!=NULL)/进行搜集 if(p = NULL) p = headj; t = ta

21、ilj; else t->next=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("nt请选择排序方法:" "nt*" "nt1.Shell排序" "nt2.Quick排序" "nt3.锦标赛排序" "

22、;nt4.堆排序" "nt5.归并排序" "nt6.基排序" "nt7.结束" "nt*"); doprintf("ntplease choose (1-7):"); getchar(); ch=getchar(); while(!(ch>'0'&&ch<'8'); return(ch);void main()int a=1; FILE *fp; char ch,filenameN; qSqList L; while(a) printf("nt请输入读入文件名:");/输入要读入的文件名 scanf("%s&quo