1.歸并排序

歸并排序的核心步驟是：

拆分：將無序數組不斷對半拆分成小塊，直到每個小塊只剩一個元素（自然有序）。
合并：將相鄰的有序小塊合并，逐步形成更大的有序塊，直到整個數組有序。

1.1 遞歸版本

遞歸天然避免越界，代碼簡潔，但遞歸深度受限。

#include <vector>
using namespace std;// 合并兩個有序子數組
void merge(int arr[], int left, int mid, int right) 
{vector<int> temp(right - left + 1);  // 臨時數組int i = left, j = mid + 1, k = 0;// 雙指針合并有序區間while (i <= mid && j <= right) {temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];}// 處理剩余元素while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];// 拷貝回原數組for (int p = 0; p < k; p++) {arr[left + p] = temp[p];}
}// 遞歸歸并排序
void mergeSort(int arr[], int left, int right) {if (left >= right) return;int mid = left + (right - left) / 2;mergeSort(arr, left, mid);//分解左半區mergeSort(arr, mid + 1, right);//分解右半區merge(arr, left, mid, right);//合并有序區間
}int main() 
{int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr)/sizeof(arr[0]);mergeSort(arr, 0, n-1);return 0;
}

1.2 非遞歸版本

非遞歸版本通過步長控制，把數組看作由多個有序子數組組成，逐步擴大子數組長度，直到整個數組有序。
非遞歸循環效率更高，適合大數據量，但是需要控制越界。

與遞歸版本不同的是遞歸是自頂向下（通過遞歸函數先拆分再合并），非遞歸是自底向上（通過數組下標直接從小塊開始合并）

假設原始數組為 [3,1,4,2,7,5]
執行步驟如下：
步長=1：把每個元素視為獨立的有序數組，兩兩合并→ 合并后 [1,3] [2,4] [5,7]
步長=2：合并相鄰的兩個長度為2的子數組→ 合并后 [1,2,3,4] [5,7]
步長=4：繼續合并更大的子數組→ 最終得到 [1,2,3,4,5,7]
?

void mergeSort(int arr[], int n) 
{// 預分配臨時空間vector<int> temp(n);  // 按步長分組（1,2,4,8...）for (int gap = 1; gap < n; gap *= 2) {// 每兩組進行比較 //[left, left+gap-1] [left+gap,left+2*gap-1]//[left,mid][mid+1, right]for (int left = 0; left < n; left += 2*gap) {// 計算子數組邊界 (按l,m,r)int mid = min(left + gap - 1, n-1);int right = min(left + 2*gap - 1, n-1);// 合并相鄰子數組int i = left, j = mid + 1, k = left;while (i <= mid && j <= right) {temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];}// 處理剩余元素while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];// 拷貝回原數組for (int p = left; p <= right; p++) {arr[p] = temp[p];}}}
}int main() 
{int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr)/sizeof(arr[0]);mergeSort(arr, n);return 0;
}

2.歸并分治

實施原理：

1. 思考問題在大范圍的答案，是否等于左部分的答案+右部分的答案+跨越左右部分的答案。
2. 計算跨越左右部分的答案時，如果左右部分各自有序，是否能讓計算跨越左右部分答案時更加便利。

分治法的基本步驟：

1. 分解：將原始數組通過遞歸的方式拆分成兩個長度相近的子數組，一直拆分到單個元素為止（因為單個元素天生有序）
2. 統計：根據題意進行相關的統計。
3. 排序：根據題意思考，在將小部分合并成大部分之前，如果將小部分進行排序，是否能便于大部分進行統計。

?

2.1 計算數組的小和

計算數組的小和

首先讓我們看一組示例 [1，3，5，2，4，6]，這個小和答案為27，其暴力解法很好想，就是每個數和其他的數進行比較進行累加，但時間復雜度是O(n^2)所以不考慮。
?
下面看看這題歸并分治的解法。

1. 根據上面說的原理，我們先看整個大范圍部分[1，3，5，2，4，6]的答案，是否可以通過左部分[1，3，5]加上右部分[2，4，6]，再加上跨越左右的答案。
首先，我們直接計算[1，3，5]小和是5，[2，4，6]小和是8。接下來計算跨越左右的答案[1，3，5] | [2，4，6]，可以看到兩邊內部的已經各種計算好了，那么跨越的先看2對應的2>1再2<3，那么對應2的小和就只有1。再看4對應的4>1,4>3,4<5那么4對應的小和就是4，6類推就是9，那么跨越的小和加起來就是14，再和前面相加14+5+8就是27答案對應上了。
2. 那么如果再把大范圍縮小到計算[1,3,5]的答案，可以看出，其左部分[1,3]小和為1，右部分[5]小和為0，跨越左右為4，相加后也對應上了小和為5。那么就可以看出小部分的解和大部分的解都是一樣的，那么就可以考慮歸并分治。
3.接下來考慮在計算跨越左右的答案時，如果左、右部分各自有序這個條件，計算會不會更簡單。
我們看[1，3，5] | [2，4，6]，如果其未排序[3,1,5] [6,2,4]，那么對于未排序的計算，需要每個數和其他數進行比較累加，就是暴力解法。肯定是更復雜的！。
4.那么這道題，保持左右各有序后計算便利在哪？
比如這個例子[3,6,7] [5,6,9]在計算跨越左右的答案時，有兩種算法。
（1）從右部分開始對左部分的數進行比對，對應5大于3，對應6>3,6>=6，對應9>3,9>6,9>7，我們可以發現，右部分下一個數的計算(如5之后的6，6之后的9)可以在上一個數的基礎上繼續計算并且加上上一個數的和。
??具體什么意思？就是比如右部分的5在和左部分3比較后再和左部分6比較，由于5<6那么左部分就到6停，下一個右部分的6直接和左部分的6進行比較，再和7比較然后停。右部分6的小和就直接加上5的小和和比較的6。右部分的9就直接加上6的小和以及比較的7。（這樣就不用右部分每一個數都和左邊的比了，因為有序）
（2）從左部分開始對右部分的數進行比對，如果5大于3，那么5后面所有的數都大于3，就直接3乘以5以及右邊的個數就行了。

兩個方法時間復雜度都是O(N)，相當于把每個數都走了一遍。
?
對應從右部分開始對左部分的數進行比對

//代表整個跨左右的答案
long long ans = 0; 
//先固定右部分的數，sum代表每個數自己的小和
for(int j = m+1, i = l, sum = 0; j <= r; ++j)
{//每個數的小和 = 這一回的比較 + 上一個數的小和while(i <= m && s[i] <= s[j]) sum+=s[i++];ans += sum;
}

對應從左部分開始對右部分的數進行比對

//代表整個跨左右的答案
long long ans = 0; 
for(int j = m+1, i = l; j <= r; ++j)
{while(i <= m && s[i] <= s[j]){ans+=(r-j+1)*s[i];++i;}
}

完整代碼

#include <iostream>using namespace std;const int MAXN = 100001;int s[MAXN];
int tmp[MAXN];long long Merge(int l, int m, int r)
{//1.先統計long long ans = 0;for(int j = m+1, i = l, sum = 0; j <= r; ++j){while(i <= m && s[i] <= s[j]) sum+=s[i++];ans += sum;}/*//計算方法二long long ans = 0; for(int j = m+1, i = l; j <= r; ++j){while(i <= m && s[i] <= s[j]){ans+=(r-j+1)*s[i++];}}*///2.再排序，方便后續部分的統計int i = l, k = l, j = m+1;while(i <= m && j <= r){tmp[k++] = (s[i] <= s[j] ? s[i++] : s[j++]);}while(i <= m) tmp[k++] = s[i++];while(j <= r) tmp[k++] = s[j++];for (int i = l; i <= r; ++i){s[i] = tmp[i];}return ans;
}long long Count(int l, int r)
{if(l == r) return 0;int m = (l+r) >> 1;//接下來進行細分，同時統計計算再排序return Count(l, m) + Count(m+1, r) + Merge(l, m, r);
}int main() {int n = 0;while(cin >> n){for(int i = 0; i < n; ++i) cin>>s[i];//首先對數組進行細分cout << Count(0, n-1) << endl;}return 0;
}

?

2.2 計算翻轉對

計算翻轉對

還是照著之前說的原理，拿[2,4,3,5,1]，分成兩個部分[2,4,3] [5,1]，在假設兩個部分分別計算好翻轉對數量以及排序后，[2,4,3] 有0個翻轉對，[5,1]是1個，統計完后因為各個內部翻轉對已經計算好了，然后想排序后對于兩邊跨越的計算是否更便利，答案是肯定的，各自排序后。那么計算跨越左右的[2,3,4][1,5]，也是有兩種方法，簡單的法一：3大于1*2了，那么排序后3之后都是大于3的，也就是都能和1能組成翻轉對的。法二：3和1比完后，接著4和5比，然后再加上3對應的翻轉對數。因為3滿足的，4也滿足。

class Solution {
public:int tmp[50001] = {0};int Merge(vector<int>& nums, int l, int m, int r){//1.統計int ans = 0;//法一// for(int i = l, j = m+1, count = 0; i <= m; ++i)// {//     while(j <= r && nums[i] > (long)2*nums[j]) count++, ++j;//     ans += count;// }//法二for(int i = l, j = m+1; i <= m; ++i){while(j <= r && nums[i] > (long)2*nums[j]){ans += (m-i+1);j++;}}//2.排序int a = l, b = l, c = m+1;while(a <= m && c <= r){tmp[b++] = (nums[a] <= nums[c] ? nums[a++] : nums[c++]);} while(a <= m) tmp[b++] = nums[a++];while(c <= r) tmp[b++] = nums[c++];for(int i = l; i <= r; ++i) nums[i] = tmp[i];return ans;}int Count(vector<int>& nums, int l, int r){if(l == r) return 0;int m = (l+r) >> 1;return Count(nums, l, m) + Count(nums, m+1, r) + Merge(nums, l, m, r);}int reversePairs(vector<int>& nums) {int len = nums.size();return Count(nums, 0, len-1);}
};

?
算法中有很多精妙又美麗的思想傳統，請務必堅持下去！！