回顧算法導論的第一個講解的算法就是歸並排序，我們把歸並排序分解為兩個步驟，第一步考慮如何進行歸並，第二步把問題分解為多次歸並排序和歸並，這是一個典型的分治思想。
每一層的調用有三個步驟：
分解：將原問題分解成若干子問題
解決：解決這些子問題，遞歸求解各個子問題。若子問題規模足夠小，則直接求解。
合並：將這些子問題的解合並成原問題的解。
要使用分治的前提是問題是線性可以合並的，如果是非線性問題，使用分治時問題將會變得很復雜。
我們將合並的數組理解為撲克牌，先把它分為兩堆牌，然後進行合並。當然數值上不會是撲克牌的數值，大家可以設想下手裡面有和他要排序數值一樣的撲克牌。
歸並排序的算法主要集中於歸並這一操作，拋開遞歸，我們單獨分析歸並這一操作，首先將兩個堆底部放入哨兵牌，可以理解為撲克牌中王一樣，它是一個還有特殊的值，為了簡化這裡放入100；結果每當顯露出哨兵牌，他不可能為較小的牌，除非兩個堆都已經顯露出哨兵牌。但這種情況一旦發生，我們的歸並操作也就結束了。因為我們事先知道剛好執行r-p+1張牌將被放置到輸出堆。
代碼如下：
[cpp]
#include <stdio.h>
#include <iostream>
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<n1;i++)
{
L[i]=A[p+i-1];
}
for(j=0;j<n2;j++)
{
R[j]=A[q+j];
}
L[n1] = 100;//代表數組中不可能出現的無窮大的數
R[n2] = 100;//<SPAN style="FONT-FAMILY: Arial, Helvetica, sans-serif">代表數組中不可能出現的無窮大的數</SPAN>
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<r)
{
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<<A[i]<<"\t";
}
cout<<endl;
system("pause");
return 0;
}
#include <stdio.h>
#include <iostream>
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<n1;i++)
{
L[i]=A[p+i-1];
}
for(j=0;j<n2;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<r)
{
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<<A[i]<<"\t";
}
cout<<endl;
system("pause");
return 0;
}
