歸并排序

歸并排序，是創建在歸并操作上的一種有效的排序算法，效率為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<n; length*=2)
 {
 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);
 }
}