歸併排序

歸併排序，是創建在歸併操作上的一種有效的排序算法，效率為O(nlogn)。1945年由約翰·馮·諾伊曼首次提出。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。速度僅次於快速排序，為穩定排序算法，一般用於對總體無序，但是各子項相對有序的數列，歸併排序的比較次數小於快速排序的比較次數，移動次數一般多於快速排序的移動次數。

歸併操作

歸併操作，也叫歸併算法，指的是將兩個已經排序的序列合併成一個序列的操作。

歸併排序原理

既然歸併排序採用的是分治法，並且依託于歸並操作，那麼其思想肯定是分而治之。我們知道歸併操作是將兩個有序的數列合併到一個有序的序列，那麼對於一個無序的長序列，可以把它分解為若干個有序的子序列，然後依次進行歸併。如果我們說每一個數字都是單獨有序的序列，那麼只要把原始長序列依次分解，直到每個子序列都只有一個元素的時候，再依次把所有的序列進行歸併，直到序列數為1

歸併排序的實現方法

遞歸法

原理如下（假設序列共有n個元素）：

1. 將原始序列從中間分為左、右兩個子序列，此時序列數為2
2. 將左序列和右序列再分別從中間分為左、右兩個子序列，此時序列數為4
3. 重複以上步驟，直到每個子序列都只有一個元素，可認為每一個子序列都是有序的
4. 最後依次進行歸併操作，直到序列數變為1

參考代碼

void Merge(int r[],int r1[],int s,int m,int t)
{
 int i=s;
 int j=m+1;
 int k=s;
 while(i<=m&&j<=t)
 {
 if(r[i]<=r[j])
 r1[k++]=r[i++];
 else
 r1[k++]=r[j++];
 }
 while(i<=m)
 r1[k++]=r[i++];
 while(j<=t)
 r1[k++]=r[j++];
 for(int l=0; l<8; l++)
 r[l]=r1[l];
}
 
void MergeSort(int r[],int r1[],int s,int t)
{
 if(s==t)
 return;
 else
 {
 int m=(s+t)/2;
 MergeSort(r,r1,s,m);
 MergeSort(r,r1,m+1,t);
 Merge(r,r1,s,m,t);
 }
}

疊代法

原理如下（假設序列共有n個元素）：

1. 將序列每相鄰兩個數進行歸併操作，形成ceil(n/2)個序列，排序後每個序列包含兩/一個元素
2. 將序列每相鄰的兩個有序子序列進行歸併操作，形成ceil(n/4)個序列，每個序列包含四/三個元素
3. 重複步驟2，直到所有元素排序完畢，即序列數為1個

參考代碼

void Merge(int*a,int low,int mid,int high)
{
 inti=low,j=mid+1,k=0;
 int *temp=(int*)malloc((high-low+1)*sizeof(int));
 while(i<=mid&&j<=high)
 a[i]<=a[j]?(temp[k++]=a[i++]):(temp[k++]=a[j++]);
 while(i<=mid)
 temp[k++]=a[i++];
 while(j<=high)
 temp[k++]=a[j++];
 memcpy(a+low,temp,(high-low+1)*sizeof(int));
 free(temp);
}
void MergeSort(int*a,int n)
{
 int length;
 for(length=1; length {
 int i;
 for(i=0; i+2*length-1<=n-1; i+=2*length)
 Merge(a,i,i+length-1,i+2*length-1);
 if(i+length<=n-1)
 　Merge(a,i,i+length-1,n-1);
 }
}