歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法镀赌，該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列玛追；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表叮贩，稱為二路歸并说莫。
歸并過程為：比較a[i]和b[j]的大小，若a[i]≤b[j]储狭，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中互婿，并令i和k分別加上1；否則將第二個(gè)有序表中的元素b[j]復(fù)制到r[k]中辽狈，并令j和k分別加上1慈参，如此循環(huán)下去，直到其中一個(gè)有序表取完刮萌，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元驮配。
歸并排序通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分掰邢，接著把左邊子區(qū)間排序娃承，再把右邊子區(qū)間排序麻削，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。
值得注意的是苏揣，歸并排序的速度僅次于快速排序弟跑，但卻是穩(wěn)定排序炭玫。
代碼一：
//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(int *r,int *rf, int i, int m, int n)
{
int j,k;
for(j=i,k=m+1; j<=m && k<=n ; ++k)
{
if(r[j] < r[i])
rf[k] = r[j++];
else
rf[k] = r[i++];
}
while(i <= m) {
rf[k++] = r[i++];
}
while(j <= n) {
rf[k++] = r[j++];
}
}
void MergeSort1(int *r, int *rf, int lenght)
{
int len = 1;
int *q = r ;
int *tmp ;
while(len < lenght) {
int s = len;
len = 2 * s ;
int i = 0;
while(i+ len <lenght){
Merge(q, rf, i, i+ s-1, i+len-1 ); //對(duì)等長的兩個(gè)子表合并
i = i+ len;
}
if(i + s < lenght){
Merge(q, rf, i, i+ s-1, lenght -1); //對(duì)不等長的兩個(gè)子表合并
}
tmp = q; q = rf; rf = tmp; //交換q,rf码党，以保證下一趟歸并時(shí)，仍從q 歸并到rf
//len = 2 * s ;
}
}
代碼二：
//將有二個(gè)有序數(shù)列a[first...mid]和a[mid...last]合并。
void MergeArray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void MergeSort2(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
//左邊有序
MergeSort2(a, first, mid, temp);
//右邊有序
MergeSort2(a, mid + 1, last, temp);
//再將二個(gè)有序數(shù)列合并
MergeArray(a, first, mid, last, temp);
}
}
