十大經典排序算法系列博客——>傳送門

---

簡介：歸并排序（MERGE-SORT）是利用歸并的思想實現的排序方法，是采用分治法Divide and Conquer的一個非常典型的應用。分Divide：將問題分成一些小的問題然后遞歸求解；治Conquer：將分的階段得到的各答案合并在一起。

算法步驟：

• 把長度為n的輸入序列分成兩個長度為n/2的子序列；

• 對這兩個子序列分別采用歸并排序；

• 將兩個排序好的子序列合并成一個最終的排序序列。

---

代碼展示

#include<bits/stdc++.h> using namespace std;void merge_sort(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;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])) //若第二個序列為空(序列1一定非空)，則復制A[p] T[i++] = A[p++]; //否則，當且僅當第一個序列非空，且較小時，復制A[p]else T[i++] = A[q++]; } for(i = x; i<y; i++) A[i]=T[i];} }int main() {int n; cin >> n; int A[n];for(int i = 0; i < n; i++) cin>>A[i];int T[n]; memset(T, 0, sizeof(T));merge_sort(A, 0, n, T);for(int i = 0; i < n; i++) cout<<A[i]<<' ';return 0; }

---

日拱一卒，功不唐捐。

總結

以上是生活随笔為你收集整理的【GIF动画+完整可运行源代码】C++实现 归并排序——十大经典排序算法之五的全部內容，希望文章能夠幫你解決所遇到的問題。

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