1. 歸并排序
歸并排序，是創建在歸并操作上的一種有效的排序演算法，效率為O(nlogn)，1945年由約翰·馮·諾伊曼首次提出，該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞回可以同時進行，速度僅次于快速排序，為穩定排序演算法，一般用于對總體無序，但是各子項相對有序的數列，歸并排序的比較次數小于快速排序的比較次數，移動次數一般多于快速排序的移動次數，
2. 歸并操作
歸并操作，也叫歸并演算法，指的是將兩個已經排序的序列合并成一個序列的操作，
3. 歸并排序原理
既然歸并排序采用的是分治法，并且依托于歸并操作，那么其思想肯定是分而治之，我們知道歸并操作是將兩個有序的數列合并到一個有序的序列，那么對于一個無序的長序列，可以把它分解為若干個有序的子序列，然后依次進行歸并，如果我們說每一個數字都是單獨有序的序列，那么只要把原始長序列依次分解，直到每個子序列都只有一個元素的時候，再依次把所有的序列進行歸并，直到序列數為1
4. 歸并排序的實作方法
遞回法
原理如下（假設序列共有n個元素）：
- 將原始序列從中間分為左、右兩個子序列，此時序列數為2
- 將左序列和右序列再分別從中間分為左、右兩個子序列，此時序列數為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個元素）：
- 將序列每相鄰兩個數進行歸并操作，形成ceil(n/2)個序列，排序后每個序列包含兩/一個元素
- 將序列每相鄰的兩個有序子序列進行歸并操作，形成ceil(n/4)個序列，每個序列包含四/三個元素
- 重復步驟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);
}
}
5. 復雜度
- 時間復雜度：O(nlogn)
- 空間復雜度：O(N)，歸并排序需要一個與原陣列相同長度的陣列做輔助來排序
- 穩定性：歸并排序是穩定的排序演算法，
temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];這行代碼可以保證當左右兩部分的值相等的時候，先復制左邊的值，這樣可以保證值相等的時候兩個元素的相對位置不變，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/65004.html
標籤：C
上一篇：C基本語法
下一篇：計算周幾的程式(基姆拉爾森公式)