欢迎来到天天文库
浏览记录
ID:38350940
大小:16.50 KB
页数:3页
时间:2019-06-10
《归并排序(非递归算法)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、#includeusingnamespacestd;voidProcess(intn);voidMergeSort(intori[],intn);voidnewMerge(intori[],inttmpArray[],ints,intn);//没有完成整个归并时,用这个函数归并两个相邻的已排序的数组voidMerge(intori[],inttmpArray[],intleft,intmid,intright);//归并两个已排好序的数组到tmpArray中voidOutput(
2、intop[],intn);//用来输出数组intmain(){intn;cin>>n;Process(n);return0;}voidProcess(intn){intori[n+1];for(inti=1;i<=n;++i)cin>>ori[i];if(n>1)//如果不止一个待排元素,就归并MergeSort(ori,n);//原始调用MergeSortelseOutput(ori,n);}voidMergeSort(intori[],intn){ints=1,tmpArray[n+1];//
3、s是每趟归并两个数组时,一个数组的长度(最后那个数组长度可能小于s)while(s4、//即最后的两个中,后面那个的长度不够s了Merge(ori,tmpArray,i,i+s-1,n);else//即归并到最后,只剩一个长度不够s的了,只需直接复制到tmpArray[]中for(;i<=n;++i)tmpArray[i]=ori[i];//至此,完成一趟归并//再copy回ori[]中,tocodeherefor(intk=0;k<=n;++k)ori[k]=tmpArray[k];Output(ori,n);}voidMerge(intori[],inttmpArray[],in5、tleft,intmid,intright){//归并两个已排好序的数组到tmpArray[]中,然后再copy回ori[]中inttmpCnt=left;//临时计数器intrightStart=mid+1;//mid其实是leftEndwhile(left<=mid&&rightStart<=right){if(ori[left]<=ori[rightStart])tmpArray[tmpCnt++]=ori[left++];elsetmpArray[tmpCnt++]=ori[rightSta6、rt++];}//下面为谁有多就把谁直接放到tmpArray[]中while(left<=mid)tmpArray[tmpCnt++]=ori[left++];while(rightStart<=right)tmpArray[tmpCnt++]=ori[rightStart++];}voidOutput(intop[],intn){for(inti=1;i<=n;++i)cout<
4、//即最后的两个中,后面那个的长度不够s了Merge(ori,tmpArray,i,i+s-1,n);else//即归并到最后,只剩一个长度不够s的了,只需直接复制到tmpArray[]中for(;i<=n;++i)tmpArray[i]=ori[i];//至此,完成一趟归并//再copy回ori[]中,tocodeherefor(intk=0;k<=n;++k)ori[k]=tmpArray[k];Output(ori,n);}voidMerge(intori[],inttmpArray[],in
5、tleft,intmid,intright){//归并两个已排好序的数组到tmpArray[]中,然后再copy回ori[]中inttmpCnt=left;//临时计数器intrightStart=mid+1;//mid其实是leftEndwhile(left<=mid&&rightStart<=right){if(ori[left]<=ori[rightStart])tmpArray[tmpCnt++]=ori[left++];elsetmpArray[tmpCnt++]=ori[rightSta
6、rt++];}//下面为谁有多就把谁直接放到tmpArray[]中while(left<=mid)tmpArray[tmpCnt++]=ori[left++];while(rightStart<=right)tmpArray[tmpCnt++]=ori[rightStart++];}voidOutput(intop[],intn){for(inti=1;i<=n;++i)cout<
此文档下载收益归作者所有