分治在排序算法中的应用
1.归并排序（分治&递归）
void Merge(int a[],int s,int m,int e,int tmp[])
{
int pb=0;
int p1=s,p2=m+1;
while(p1<=m&&p2<=e)
{
if(a[p1]<a[p2])
tmp[pb++]=a[p1++];
else tmp[pb++]=a[p2++];
}
while(p1<=m)
tmp[pb++]=a[p1++];
while(p2<=e)
tmp[pb++]=a[p2++];
for(int i=0;i<e-s+1;i++)
a[s+i]=tmp[i];
}
void MergeSort(int a[],int s,int e,int tmp[])
{
if(s<e)
{
int middle=(e+s)/2;
int tmp1[100],tmp2[100];
MergeSort(a,s,middle,tmp);
MergeSort(a,middle+1,e,tmp+middle-s);
Merge(a,s,middle,e,tmp);
}
}
2.快速排序（分治&递归）
void swap(int &a,int &b)
{
int tmp=a;
a=b;
b=tmp;
}
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(j>i&&a[i]<=k) i++;
swap(a[i],a[j]);
}//处理完后，a[i]=k;
Quicksort(a,s,i-1);
Quicksort(a,i+1,e);
}
