归并排序(非递归算法)

《归并排序(非递归算法)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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(s

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<