歸併就是將多個已排序的數列合成一個有序的數列。將兩個有序序列合併為一個有序序列叫二路歸併(merge)。歸併排序就是利用"歸併"技術來進行排序，兩兩歸併最後變為有序的序列。
基本介紹
- 中文名：並歸排序法
- 目的：合成一個有序的數列
- 技術："歸併"技術
- 兩兩歸併：最後變為有序的序列
基本思路,參考代碼,
基本思路
1、算法基本思路
設有兩個有序（升序）序列存儲在同一數組中相鄰的位置上，不妨設為A[l..m]，A[m+1..h]，將它們歸併為一個有序數列，並存儲在A[l..h]。
為了減少數據移動次數，不妨採用一個臨時工作數組C，將中間排序結果暫時保存在C數組中，等歸併結束後，再將C數組值複製給A。
歸併過程中，設定p1，p2和p3三個指針，其初值分別指向三個有序區的起始位置。歸併時依次比較A[p1]和A[p2]的關鍵字，取關鍵字較小的記錄複製到C[p3]中，然後將被複製記錄的指針p1或p2加1，以及指向複製位置的指針p3加1。
重複這一過程直至有一個已複製完畢，此時將另一序列中剩餘數據依次複製到C中即可。
2）（1）自底向上的基本思想
自底向上的基本思想是：第1趟歸併排序時，將數列A[1..n]看作是n個長度為1的有序序列，將這些序列兩兩歸併，若n為偶數，則得到[n/2]個長度為2的有序序列；若n為奇數，則最後一個子序列不參與歸併。第2趟歸併則是將第1趟歸併所得到的有序序列兩兩歸併。如此反覆，直到最後得到一個長度為n的有序檔案為止。
上述的每次歸併操作，均是將兩個有序序列合併成一個有序序列，故稱其為“二路歸併排序”。
思路
歸併（Merge）排序法是將兩個（或兩個以上）有序表合併成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列。
參考代碼
void mergSort(int* a,int low,int mid,int high)
{
int * p=new int[high+1];
int i=low;
int j=low;
int h=mid+1;
while(h<=high&&j<=mid)
{
if(a[j]<=a[h])
{
p[i]=a[j];
j++;
i++;
}
else
{
p[i]=a[h];
h++;
i++;
}
}
for(;j<=mid;j++,i++)
{
p[i]=a[j];
}
for(;h<=high;h++,i++)
{
p[i]=a[h];
}
for(i=low;i<=high;i++)
{
a[i]=p[i];
}
delete[] p;
}
void merg(int* a,int low,int high)
{
if(low<high)
{
int mid=(low+high)/2;
merg(a,low,mid);
merg(a,mid+1,high);
mergSort(a,low,mid,high);
}
}
