歸併排序[從入門到放棄]
- 2019 年 11 月 2 日
- 筆記
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++];這行程式碼可以保證當左右兩部分的值相等的時候，先複製左邊的值，這樣可以保證值相等的時候兩個元素的相對位置不變。
