文章目錄
- 1.歸并排序
- 1.1 遞歸版本
- 1.2 非遞歸版本
- 2.歸并分治
- 2.1 計算數組的小和
- 2.2 計算翻轉對
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.歸并分治
實施原理:
- 思考問題在大范圍的答案,是否等于左部分的答案+右部分的答案+跨越左右部分的答案。
- 計算跨越左右部分的答案時,如果左右部分各自有序,是否能讓計算跨越左右部分答案時更加便利。
分治法的基本步驟:
- 分解:將原始數組通過遞歸的方式拆分成兩個長度相近的子數組,一直拆分到單個元素為止(因為單個元素天生有序)
- 統計:根據題意進行相關的統計。
- 排序:根據題意思考,在將小部分合并成大部分之前,如果將小部分進行排序,是否能便于大部分進行統計。
?
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);}
};
?
算法中有很多精妙又美麗的思想傳統,請務必堅持下去!!