回顾算法导论的第一个讲解的算法就是归并排序，我们把归并排序分解为两个步骤，第一步考虑如何进行归并，第二步把问题分解为多次归并排序和归并，这是一个典型的分治思想。
每一层的调用有三个步骤：
分解：将原问题分解成若干子问题
解决：解决这些子问题，递归求解各个子问题。若子问题规模足够小，则直接求解。
合并：将这些子问题的解合并成原问题的解。
要使用分治的前提是问题是线性可以合并的，如果是非线性问题，使用分治时问题将会变得很复杂。
我们将合并的数组理解为扑克牌，先把它分为两堆牌，然后进行合并。当然数值上不会是扑克牌的数值，大家可以设想下手里面有和他要排序数值一样的扑克牌。
归并排序的算法主要集中于归并这一操作，抛开递归，我们单独分析归并这一操作，首先将两个堆底部放入哨兵牌，可以理解为扑克牌中王一样，它是一个还有特殊的值，为了简化这里放入100；结果每当显露出哨兵牌，他不可能为较小的牌，除非两个堆都已经显露出哨兵牌。但这种情况一旦发生，我们的归并操作也就结束了。因为我们事先知道刚好执行r-p+1张牌将被放置到输出堆。
代码如下：
[cpp]
#include
#include
using namespace std;
void Merge(int* A,int p,int q,int r)
{
int n1= q-p+1;
int n2= r-q;
int *L= new int[n1+1];
int *R= new int[n2+1];
int i=0;
int j=0;
for(i=0;i
L[i]=A[p+i-1];
}
for(j=0;j
R[j]=A[q+j];
}
L[n1] = 100;//代表数组中不可能出现的无穷大的数
R[n2] = 100;//代表数组中不可能出现的无穷大的数
i = 0;
j = 0;
for(int k = p-1;k < r; k++)
{
if(L[i]<=R[j])
{
A[k] = L[i];
i = i+1;
}
else
{
A[k] = R[j];
j = j+1;
}
}
}
void Merge_Sort(int *A,int p,int r)
{
if(p
int q=(p+r)/2;
Merge_Sort(A,p,q);
Merge_Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
int A[15] = {11,12,13,14,15,1,2,3,4,5,6,7,8,9,10};
int main(int argc, char **argv)
{
Merge_Sort(A,1,15);
for(int i=0;i<15;i++)
{
cout<
cout<
return 0;
}
#include
#include
using namespace std;
void Merge(int* A,int p,int q,int r)
{
int n1= q-p+1;
int n2= r-q;
int *L= new int[n1+1];
int *R= new int[n2+1];
int i=0;
int j=0;
for(i=0;i
L[i]=A[p+i-1];
}
for(j=0;j
R[j]=A[q+j];
}
L[n1] = 100;//代表数组中不可能出现的无穷大的数
R[n2] = 100;//代表数组中不可能出现的无穷大的数
i = 0;
j = 0;
for(int k = p-1;k < r; k++)
{
if(L[i]<=R[j])
{
A[k] = L[i];
i = i+1;
}
else
{
A[k] = R[j];
j = j+1;
}
}
}
void Merge_Sort(int *A,int p,int r)
{
if(p
int q=(p+r)/2;
Merge_Sort(A,p,q);
Merge_Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
int A[15] = {11,12,13,14,15,1,2,3,4,5,6,7,8,9,10};
int main(int argc, char **argv)
{
Merge_Sort(A,1,15);
for(int i=0;i<15;i++)
{
cout<
cout<
return 0;
}