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

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;/統(tǒng)計(jì)移動(dòng)次數(shù)long comparetimes;/統(tǒng)計(jì)比較次數(shù)qSqList creat(char filename)/讀入文件并且將數(shù)據(jù)保存FILE *fp;long i;qSqList L;L=(qSqList)malloc(LEN);L->l

3、ength=0;if(fp=fopen(filename,"r")=NULL)/文件不存在時(shí)終止程序 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+;/記錄讀入的數(shù)據(jù)長度fclose(fp); return(L);void Print2(qSqList

4、 L)/將序列輸出到指定的文件中l(wèi)ong i;FILE *fp;char filenameN; printf("nt請(qǐng)輸入存儲(chǔ)文件名："); scanf("%s",filename);/輸入將要儲(chǔ)存的文件名 fp=fopen(filename,"w"); for(i=1;i<=L->length;i+)/將鏈表中數(shù)據(jù)逐一寫入文件中fprintf(fp,"%d (%d)n",L->ri.key,L->ri.num); fclose(fp);void Print(qSqList L)/打印數(shù)據(jù)個(gè)

5、數(shù)以及排序過程中的比較次數(shù)和移動(dòng)次數(shù)printf("nt數(shù)據(jù)個(gè)數(shù):%ld",L->length); printf("nt比較次數(shù):%ld",comparetimes); printf("nt移動(dòng)次數(shù):%ld",shifttimes);struct node Min1(struct node a,struct node b)/比較兩接點(diǎn)關(guān)鍵字的大小struct node temp; if(a.key>b.key)temp=b;else temp=a; comparetimes+; return(temp);qSqList s

6、hellinsert(qSqList L,int dk)/對(duì)順序表以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暫時(shí)存儲(chǔ)在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;/計(jì)算排序增量 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;/用序列的第一個(gè)記錄作樞軸記錄 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)/對(duì)順序表L中的子序列L.rlow.high作快速排序long pivot; if(low<high)/序列長度大于1pivot=Quicksort(L,low,high);/將序列一分為二 Quick2(L,low,pivot-1);/對(duì)低位子表遞歸排序 Quick2(L,pivot+1,high);/對(duì)高位子表遞歸排序 return(L);qSqList

11、Quick(qSqList L)/對(duì)順序表作快速排序long low,high; low=1;/將第一個(gè)數(shù)據(jù)所在位置定義為低位 high=L->length;/將最后一個(gè)數(shù)據(jù)所在位置定義為高位 L=Quick2(L,low,high);/對(duì)順序表作快速排序 Print(L); Print2(L); return(L);void TourSort(SqList *L,long n)/錦標(biāo)賽排序 qSqList Lp; long i=0,t=1,k=1,w; while(t<n)/t表示完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)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)/調(diào)整L->s的關(guān)鍵字，使L->rs.m成為一個(gè)大頂堆long j; struct node rc; rc=L->rs; for(j=2*s;j<=m;j*=2)/沿key較大的接點(diǎn)向下篩選 if(j<m&&j<(L->rj.key,L->rj+1.key)/j為key較大的記錄的下標(biāo)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)/將堆頂記錄和當(dāng)前未經(jīng)排序子序列中最后一個(gè)記錄交換L->r0=L->r1; L->r1=L->ri; L->ri=

16、L->r0; shifttimes=shifttimes+3; Heapadjust(L,1,i-1);/將L重新調(diào)整為大頂堆 Print(L); Print2(L); return(L);void Merge(qSqList L,int low,int m,int high)/將兩個(gè)有序表Rlow.mhe Rm+1.high歸并為一個(gè)有序表Rlow,highint i=low,j=m+1,k=0;/k是temp的下標(biāo)，i,j分別為第1，2段的下標(biāo) struct node *temp; temp=(struct node*)malloc(high-low+1)*sizeof(struct

17、 node);/用于臨時(shí)保存有序序列 while(i<=m&&j<=high)/在第1段和第2段均未掃描完時(shí)循環(huán) 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段余下的部分復(fù)制到temp tempk=L->ri; k+; i+; while(j<=high)/將第2段余下的部分復(fù)制到temp tempk=L->rj; k+;

18、j+; for(k=0,i=low;i<=high;i+,k+)/將temp復(fù)制回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)/基數(shù)排序int g

19、,i,j,k,d=2; struct node2 *p,*s,*t,*head10,*tail10;/定義各鏈隊(duì)的首尾指針 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; /初始化各鏈隊(duì)首、尾指針 while(p!=NULL)/對(duì)于原鏈表中的每個(gè)結(jié)點(diǎn)循環(huán) k = p->r.key/d; k = k%10; if(headk=NULL)/進(jìn)行分配 headk=p; tailk=p; else tailk->next=p; tailk=p; p = p->next;/取下一個(gè)待排序的元素 p=NULL; for(j=0;j<10;j+)/對(duì)每一個(gè)鏈隊(duì)循環(huán) if(headj!=NULL)/進(jìn)行搜集 if(p = NULL) p = headj; t = ta

21、ilj; else t->next=headj; t = tailj; t->next=NULL;/最后一個(gè)結(jié)點(diǎn)的next置為空 d=d*10; i=1; while(p!=NULL) L->ri = p->r; i+; p=p->next; Print2(L);char chmenu()/對(duì)排序方法進(jìn)行選擇char ch; printf("nt請(qǐng)選擇排序方法:" "nt*" "nt1.Shell排序" "nt2.Quick排序" "nt3.錦標(biāo)賽排序" "

22、;nt4.堆排序" "nt5.歸并排序" "nt6.基排序" "nt7.結(jié)束" "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請(qǐng)輸入讀入文件名:");/輸入要讀入的文件名 scanf("%s&quo