分治法合并排序

发布时间:2016-12-11 4:49:22 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"分治法合并排序",主要涉及到分治法合并排序方面的内容,对于分治法合并排序感兴趣的同学可以参考一下。

分治法是递归的设计方法,理解成一回事好了。 一句话说清思路: 1.将两个已经排好序的数组进行合并,合并的时候也是按大小进行合并 2.将需要排序的数组进行拆分,分成左右两个数组,之后进行排序,然后进行合并 3.递推的停止条件为分开的数组只有一个数了。则不分左右。 #include "stdafx.h" #include <iostream> using namespace std; void Show(int *p,int length) { for(int i=0;i<length;i++) { cout<<p[i]; cout<<" "; } } // void Merage(int *p1,int p1Length,int *p2,int p2Length,int *buffer) { int i=0; int j=0; int pBuffer=0; while(i<p1Length&&j<p2Length) { if(p1[i]<p2[j]) { buffer[pBuffer]=p1[i]; i++; } else { buffer[pBuffer]=p2[j]; j++; } pBuffer++; } while(i<p1Length) { buffer[pBuffer]=p1[i]; pBuffer++; i++; } while(j<p2Length) { buffer[pBuffer]=p2[j]; pBuffer++; j++; } } void Sort(int *pBuf,int length,int *afterSortBuf) { if(length>1) { int leftP=length/2; int rightP=length-leftP; Sort(pBuf,leftP,afterSortBuf); Sort(pBuf+leftP,rightP,afterSortBuf); Merage(pBuf,leftP,pBuf+leftP,rightP,afterSortBuf); for(int i=0;i<length;i++) { pBuf[i]=afterSortBuf[i]; } } } int _tmain(int argc, _TCHAR* argv[]) { int needSort[]={9,3,9,9,2,9,8,7,-9,10}; int sortBuf[10]; Sort(needSort,10,sortBuf); Show(needSort,10); int k=0; cin>>k; return 0; }

上一篇:switch中的参数类型问题
下一篇:GitHub详细教程

相关文章

相关评论