歸并排序算法

1.劃分問題：把序列分成元素個數盡量相等的兩半。

2.遞歸求解：把兩半元素分別排序。

3.合并問題：把兩個有序表合并成一個。

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。

算法代碼

void merge_sort(int *A, int x, int y, int *T) {if (y - x > 1) //等價于x+1<y，即左半部分的右邊界還在右半部分的左邊界左邊{int m = x + (y - x) / 2;//劃分int p = x, q = m, i = x;merge_sort(A, x, m, T);//遞歸求左解merge_sort(A, m, y, T);//遞歸求右解while (p < m || q < y){if (q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++];//從左半數組復制到臨時空間else T[i++] = A[q++];//從右半數組復制到臨時空間}for (i = x; i < y; ++i) A[i] = T[i];//從輔助空間復制回A數組} }

動圖演示

實戰演練

#include <iostream>using namespace std; int A0[15] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; int T0[15];void merge_sort(int *A, int x, int y, int *T) {if (y - x > 1) //等價于x+1<y，即左半部分的右邊界還在右半部分的左邊界左邊{int m = x + (y - x) / 2;//劃分int p = x, q = m, i = x;merge_sort(A, x, m, T);//遞歸求左解merge_sort(A, m, y, T);//遞歸求右解while (p < m || q < y){if (q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++];//從左半數組復制到臨時空間else T[i++] = A[q++];//從右半數組復制到臨時空間}for (i = x; i < y; ++i) A[i] = T[i];//從輔助空間復制回A數組} }int main() {for (int m = 0; m < 15; ++m) {cout << A0[m] << ' ';}cout << endl;merge_sort(A0, 0, 15, T0);for (int n = 0; n < 15; ++n) {cout << A0[n] << ' ';}cout << endl;return 0; } 3 44 38 5 47 15 36 26 27 2 46 4 19 50 48 2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

算法精講

首先，只要有一個序列非空，就要繼續合并（while (p < m || q < y)），因此在比較時不能直接比較A[p]和A[q]，因為可能其中一個序列為空，從而A[p]或者A[q]代表的是一個實際不存在的元素。
~如果第二個排序為空（此時第一個序列一定非空），復制A[p];
~否則（第二個序列非空），當且僅當第一個序列也非空，且A[p]<=A[q]時，才復制A[p]。

算法分析

歸并排序是一種穩定的排序方法。和選擇排序一樣，歸并排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是O(nlogn）的時間復雜度。代價是需要額外的內存空間。

逆序對問題

給一列數a₁,a₂,……,a_n，求它的逆序對數，即有多少個有序對（i,j），使得i<j但a_i>a_j。n可以高達10⁶。

分析

分治三步法：
“劃分問題”：把序列分成元素個數盡量相等的兩半；
“遞歸求解”：統計i和j均在左邊或者右邊的逆序對個數；
“合并問題”：統計i在左邊，但j在右邊的逆序對個數。

關鍵在于合并：如何求出i在左邊，而j在右邊的逆序對數目？
統計的常見技巧是“分類”：只要對于右邊的每個j，統計左邊比它大的元素的個數f(i)，則所有f(j)之和便是答案。

歸并排序可以“順便”完成f(j)的計算：由于合并操作是從小到大進行的，當右邊的A[j]復制到T中時，左邊還沒來得及復制到T的那些數就是左邊所有比A[j]大的數，此時在累加器中加上左邊元素個數m-p即可（左邊所剩的元素在區間[p,m)中，因此元素個數為m-p）。

代碼

#include <iostream> using namespace std; int cnt=0,T0[15]; int A0[15] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; void Reverse(int *A,int x,int y,int *T) {if (y>x+1){int m=x+(y-x)/2;int p=x,q=m,i=x;Reverse(A,x,m,T);Reverse(A,m,y,T);while (p<m||q<y){if (q>=y||(p<m&&A[p]<=A[q]))T[i++]=A[p++];else{T[i++]=A[q++];cnt+=m-p;}}for (int i = x; i < y; ++i)A[i]=T[i];} } int main() {Reverse(A0, 0, 15, T0);cout<<"cnt="<<cnt<<endl;return 0; }

總結

以上是生活随笔為你收集整理的排序算法 —— 归并排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。