所谓归并排序，就是把一段需要排序的序列分成2部分，分别完成排序之后，然后进行合并，从而完成对整个序列的排序。众所周知，归并排序用了分治的思想，即把原任务分成和原任务相同，但规模更小的几个子问题。分别解决，从而达到解决原问题的效果。
ex:给定以下数组a[10]={ 6 ,5 ,7 ,1 ,4 ,3 ,2 ,5 ,9 ,8}，要求按从大到小的顺序排序，归并的思路如下：
1.将其分成两部分6 5 7 1 4 和 3 2 5 9 8
2.(以前半部分为例，下同)显然需要继续分，前半部分分成 6 5 7 和1 4，
3.再次分成 6 5 和 7
4.将 6 5分成 6 和5
5.接下来就是归并了，归并函数Merge()里有两个"指针"，记录两部分的头，然后分别进行比较，将小的(或大的)先放在b[]数组里，比如对以上过程，先放5，再放6，放好之后拷贝进原数组，再与上次分好的进行比较，放7，以此类推(即新的组里的每一个元素都需要比较，而不是简单的与排好的部分首元素或者尾元素比较)，如何让它回到上层呢，由此很自然想到递归解决。
代码如下：
#include <iostream> using namespace std; void Sort(int a[],int m,int n,int b[]); void Merge(int a[],int m,int k,int n,int b[]); int *a; int *b; int main() { int n; cin>>n; a=new int [n]; b=new int [n]; for(int i=0;i<n;i++) cin>>a[i]; Sort(a,0,n-1,b); for(int i=0;i<n;i++) cout<<a[i]<<" "; return 0; } void Sort(int *a,int m,int n,int b[]) { if(m<n) { int k=m+(n-m)/2; Sort(a,m,k,b); Sort(a,k+1,n,b); Merge(a,m,k,n,b); } } void Merge(int a[],int m,int k,int n,int b[]) { int pb=0; int p1=m,p2=k+1; while(p1<=k&&p2<=n) { if(a[p1]<a[p2]) b[pb++]=a[p1++]; else b[pb++]=a[p2++]; } while(p1<=k) b[pb++]=a[p1++]; while(p2<=n) b[pb++]=a[p2++]; for(int i=0;i<n-m+1;++i) a[m+i]=b[i]; }
好了，既然已经掌握了归并排序，接下来我们再来看一个排序——快速排序。
同样是分治的思想，同样是刚才的数组，具体怎么实现排序呢。
1.我们选择一个标记数字，方便起见，选择a[0],令k=a[0]
2.将比a[0]小的数移动到a[0]的左边，比a[0]大的数移动到a[0]的右边，例如，对于6 ,5 ,7 ,1 ,4 ,3 ,2 ,5 ,9 ,8，a[0]=6,设置一个i，j分别从第一个和最后一个位置开始(即i=0，j=9)，首先从j开始，此时i=0,如果a[j]>=k,--j,否则交换a[j],a[i],得到5,5,7,1,4,3,2,6,9,8,接下来j停止，从i开始，如果a[i]<k,++i,否则交换a[i],a[j],得到5,5,2,1,4,3,7,6,9,8,继续从j开始,发现已经没有比k还大的数了，程序会一直--j,直到i=j，此时我们跳出循环
3.数组已经被分成6左边的和右边的两部分，此时我们继续按步骤2对左右两部分进行处理，一直处理到只剩下一个数(递归终止条件)，就可以得到我们想要的结果了。
代码如下：
#include <iostream> using namespace std; int b[10]={1,0,7,5,6,9,8,4,3,2}; void swap(int &a,int &b); void quicksort(int a[],int s,int e); int main() { quicksort(b,0,9); for(int i=0;i<10;i++) cout<<b[i]<<" "; return 0; } void swap(int &a,int &b) { int temp=a; a=b; b=temp; } void quicksort(int a[],int s,int e) { if(s>=e) return; int k=a[s]; int i=s,j=e; while(i!=j) { while(j>i&&a[j]>=k) --j; swap(a[i],a[j]); while(i<j&&a[i]<=k) ++i; swap(a[i],a[j]); } quicksort(a,s,i-1); quicksort(a,i+1,e); }
以上就是分治之归并排序，快速排序了，如有什么疏漏的地方和不足之处，欢迎批评指正。。。