排序代码

#includestdio.h#includestdlib.hstructnode{intkey;}r[20];structrnode{intkey;intpoint;};main(){voidprint(structnodea[20],intn);intcreat();voidshell(structnodea[20],intn);inthoare(structnodea[20],intl,inth);voidquick1(structnodea[20],intn);voidquick2(structnodea[20],intl,inth);voidheap(structnodea[20],inti,intm);voidheapsort(structnodea[20],intn);voidmerges(structnodea[20],structnodea2[20],inth1,intmid,inth2);voidmergepass(structnodea[20],structnodea2[20],intl,intn);voidmergesort(structnodea[20],intn);intyx(intm,inti);intradixsort(structrnodea[20],intn);intnum,l,h,c;structrnodes[20];c=1;while(c!=0){printf(主菜单\n);printf(1输入关键字，以-9999表示结束。\n);printf(2希尔排序\n);printf(3非递归的快速排序\n);printf(4递归的快速排序\n);printf(5堆排序\n);printf(6归并排序\n);printf(7基数排序\n);printf(输入选择(1--7,0表示结束):);scanf(%d,&c);switch(c){case1:num=creat();print(r,num);break;case2:shell(r,num);print(r,num);break;case3:quick1(r,num);print(r,num);break;case4:l=0;h=num-1;quick2(r,l,h);printf(outputquick2sortresult:\n);print(r,num);break;case5:heapsort(r,num);break;case6:mergesort(r,num);print(r,num);break;case7:radixsort(s,num);}}}//mainendvoidprint(structnodea[20],intn){inti;for(i=0;in;i++)printf(%5d,a[i].key);printf(\n);}//printendintcreat(){inti,n;n=0;printf(inputkeys);scanf(%d,&i);while(i!=-9999){r[n].key=i;n++;scanf(%d,&i);}return(n);}//createndvoidshell(structnodea[20],intn)//希尔排序{inti,j,k;for(i=n;i=1;i--)a[i].key=a[i-1].key;k=n/2;while(k=1){for(i=k+1;i=n;i++){a[0].key=a[i].key;j=i-k;while((a[j].keya[0].key)&&(j=0)){a[j+k].key=a[j].key;j=j-k;}a[j+k]=a[0];}k=k/2;}for(i=0;in;i++)a[i].key=a[i+1].key;printf(输出希尔排序的结果:\n);}//shellend////////////////////快速排序///////////////////////////inthoare(structnodea[20],intl,inth)//分区处理函数{inti,j;structnodex;i=l;j=h;x.key=a[i].key;do{while((ij)&&(a[j].key=x.key))j--;if(ij){a[i].key=a[j].key;i++;}while((ij)&&(a[i].key=x.key))i++;if(ij){a[j].key=a[i].key;j--;}}while(ij);a[i].key=x.key;return(i);}//hoareendvoidquick1(structnodea[20],intn){inti,l,h,tag,top;ints[20][2];l=0;h=n-1;tag=1;top=0;do{while(lh){i=hoare(a,l,h);top++;s[top][0]=i+1;s[top][1]=h;h=h-1;}if(top==0)tag=0;else{l=s[top][0];h=s[top][1];top--;}}while(tag==1);printf(输出非递归快速排序结果:\n);}//quickendvoidquick2(structnodea[20],intl,inth)//递归的快速排序{inti;if(lh){i=hoare(a,l,h);quick2(a,l,i-1);quick2(a,i+1,h);}}//quick2end////////////////////快速排序结束////////////////////////////////////////////堆排序函数//////////////////////////voidheap(structnodea[20],inti,intm)//调整堆的函数{structnodex;intj;x.key=a[i].key;j=2*i;while(j=m){if(jm)if(a[j].keya[j+1].key)j++;if(a[j].keyx.key){a[i].key=a[j].key;i=j;j=2*i;}elsej=m+1;}a[i].key=x.key;}//heapendvoidheapsort(structnodea[20],intn)//堆排序的主体函数{inti,v;structnodex;for(i=n;i0;i--)a[i].key=a[i-1].key;for(i=n/2;i=1;i--)heap(a,i,n);printf(输出堆排序结果:\n);for(v=n;v=2;v--){printf(%5d,a[1].key);x.key=a[1].key;a[1].key=a[v].key;a[v].key=x.key;heap(a,1,v-1);}printf(%5d,a[1].key);for(i=0;in;i++)a[i].key=a[i+1].key;}//heapsortend/////////////////堆排序函数结束/////////////////////////////////////归并函数////////////////////////voidmerges(structnodea[20],structnodea2[20],inth1,intmid,inth2)//归并排序的核心算法{inti,j,k;i=h1;j=mid+1;k=h1-1;while((i=mid)&&(j=h2)){k=k+1;if(a[i].key=a[j].key){a2[k].key=a[i].key;i++;}else{a2[k].key=a[j].key;j++;}}while(i=mid){k++;a2[k].key=a[i].key;i++;}while(j=h2){k++;a2[k].key=a[j].key;i++;}}//mergesendvoidmergepass(structnodea[20],structnodea2[20],intl,intn)//一趟归并{intj,i,h1,mid,h2;i=0;while((n-i)=2*l){h1=i;mid=h1+l-1;h2=i+2*l-1;merges(a,a2,h1,mid,h2);i=i+2*l;}if((n-i)=l)for(j=i;j=n;j++)a2[j].key=a[j].key;else{h1=i;mid=h1+l-1;h2=n-1;merges(a,a2,h1,mid,h2);}}//mergepassendvoidmergesort(structnodea[20],intn){intl;structnodea2[20];l=1;while(ln){mergepass(a,a2,l,n);l=2*l;mergepass(a2,a,l,n);l=2*l;}printf(输出归并排序的结果:\n);}//mergesortend///////////////归并函数结束//////////////////////////////基数排序///////////////////intyx(intm,inti)//分离关键字倒数第i位有效数字的算法{intx;switch(i){case1:x=m%10;break;case2:x=(m%100)/10;break;case3:x=(m%1000)/100;break;case4:x=(m%10000)/1000;break;}return(x);}//yxendintradixsort(structrnodea[20],intn){intf[11],e[11],i,j,k,l,p,d,t;for(i=1;i=n;i++){a[i].key=r[i-1].key;a[i].point=i+1;}a[n].point=0;p=1;printf(输出关键字有效位数d\n);scanf(%d,&d);printf(输出基数排序的结果:\n);for(i=1;i=d;i++){for(j=0;j=10;j++){f[j]=0;e[j]=0;}while(p!=0){k=yx(a[p].key,i);if(f[k]==0){f[k]=p;e[k]=p;}else{l=e[k];a[l].point=p;e[k]=p;}p=a[p].point;}j=0;while(f[j]==0)j++;p=f[j];t=e[j];while(j10){j++;while((j10)&&(f[j]==0))j++;if(f[j]!=0){a[t].point=f[j];t=e[j];}}a[t].point=0;t=p;while(t!=0){printf(%5d,a[t].key);t=a[t].point;}printf(\n);}return(p);}