数据结构查找排序算法.doc

注：下面所有算法顺序结构都为typedef structKeyType key;OthorType otherdata;typedef struct RecordType rmaxsize+1; int length;SqeList;二分查找： int BInSrch(RecordList *L,KeyType k) int low=0,i=0; int high=L-lengh-1; while(low=high) int mid=(low+high)/2; if(k=rmid.key) i=mid;break; else if(krmid.key) high=mid-1; else low=mid+1; return(i); 直接插入排序法： void InsertSort(SqeList *L) for(i=1;ilength;i+) L-r0=L-ri;j=i-1; while(L-r0.keyrj.key) L-rj+1=L-rj; j=j-1; L-rj+1=L-r0; 希尔排序 void ShellInsert(SqeList *L,int di) for(i=l+di;ilength;i+) if(L-ri.keyri-di.key) L-t0=L-ri; for(j=i-di;(j0)&(L-r0.keyrj.key);j-=di) L-rj+di=L-rj; L-rj+di=L-r0; void ShellSort(SqeList *L,int delta,int n) for(i=0;ilength; change=1; for(i=0;jn-i-1&change;+i) change=0; for(j=0;jrj.keyL-rj+1.key) x=L-rj; L-rj=L-rj+1; L-rj+1=x;change=1; 快速排序： int Partition(SqeList *H,int left,int right) RecordType x; int low,high;x=H-rleft; low=left;high=right; while(lowrhigh.key=x.key&lowhigh) high-; if(lowrlow=H-rhigh; low+; while(H-rlow.keyx.key&lowhigh) low+; if(lowrhigh=H-rlow; H-rlow=x; return low; void QuickSort(SqeList *L,int low,int high) int mid; if(lowlength; for(i=0;in-1;+i) k=i; for(j=i+1;jrj.keyrk.key) k=j; if(k!=i) x=L-ri; L-ri=L-rk; L-rk=x; 归并排序：void Merge(RecordType r,RecordType r1,int low,int mid,int high) int i,j,k; i=low;j=mid+1;k=low; while(i=mid&j=high) if(ri.key=rj.key) r1k=ri; +i; else r1k=rj; +j; +k; while(i=mid) r1k+=ri+; while(j=mid) r1k+=rj+;void Mergepass(RecordType r,RecordType r1,int len) int j,i=0; while(i+len*2=n) Merge(r,r1,i,i+len-1,i+len*2-1); i=i+len*2; if(i+len-1n-1) Merge(r,r1,i,i+len-1,n-1); else for(j=i;jn;j+) r1j=rj;void MergeSort(SqeList L) int len,n; RecordType *r1; n=L.length;len=1; r1=(RecordType*)malloc(sizeof(ReordType)*n); whil