数据结构8645归并排序(非递归算法).doc

《数据结构8645归并排序(非递归算法).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、#include#defineMAXSIZE100typedefintKeytype;typedefstruct{Keytypekey;}recordtype;typedefstruct{recordtyper[MAXSIZE+1];intlength;}table;voidvisit(table*t){inti;for(i=1;i<=t->length;i++)printf("%d",t->r[i].key);}voidmerge(table*tabs,table*tabg,intu,intm,intv){inti,j,k,t;i=u;j=m+1

2、;k=u;while(i<=m&&j<=v){if(tabs->r[i].key<=tabs->r[j].key){tabg->r[k]=tabs->r[i];i++;}else{tabg->r[k]=tabs->r[j];j++;}k++;}if(i<=m)for(t=i;t<=m;t++)tabg->r[k+t-i]=tabs->r[t];elsefor(t=j;t<=v;t++)tabg->r[k+t-j]=tabs->r[t];}voidmergepass(table*tabs,table*tabg,intlen){inti,j,n;n=tabg->leng

3、th=tabs->length;i=1;while(i<=n-2*len+1){merge(tabs,tabg,i,i+len-1,i+2*len-1);i=i+2*len;}if(i+len-1r[j]=tabs->r[j];}voidmergesort(table*tab){intlen;tabletemp;len=1;while(lenlength){mergepass(tab,&temp,len);visit(&temp);pri

4、ntf("");len=2*len;*tab=temp;}}intmain(){inti;tabletab;scanf("%d",&tab.length);for(i=1;i<=tab.length;i++)scanf("%d",&tab.r[i].key);mergesort(&tab);return0;}