歸并排序

歸并排序是一種分治算法，怎么分，怎么治？

• 分：通過遞歸不斷把數組分成兩半，直到每個子數組只剩 1 個元素（天然有序）
• 治：把兩個已經排好序的子數組合并成一個有序數組。

把問題分解為簡單子問題，就體現在每個數組只剩一個元素時，那就天然有序了。

模板題

P1177 【模板】排序

歸并排序代碼實現

#include<iostream>using namespace std;const int N = 1e5 + 10;int n, a[N], tmp[N]; //a存數據，tmp輔助歸并排序時合并兩個數組 void merge_sort(int left, int right)
{if(left >= right) return; //left == right只有一個元素，有序，返回 //1.數組一分為二 int mid = (left + right) / 2;//2.將左右數組都排好序 merge_sort(left, mid);merge_sort(mid + 1, right);//3.合并左右有序數組到tmp中 int cur1 = left, cur2 = mid + 1, i = left; //i幫助寫入臨時數組 while(cur1 <= mid && cur2 <= right){if(a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];else tmp[i++] = a[cur2++];}while(cur1 <= mid) tmp[i++] = a[cur1++];while(cur2 <= right) tmp[i++] = a[cur2++];//4.將tmp中的[left,right]區間轉移到a的[left,right]區間 for(int j=left;j<=right;j++) a[j] = tmp[j]; //最容易錯的一步，要知道在merge_sort函數中，我們是對[left, right]區間進行排序而不是[0, n] 
}int main()
{cin >> n;for(int i=1;i<=n;i++) cin >> a[i];merge_sort(1,n);for(int i=1;i<=n;i++) cout << a[i] << " ";return 0;
}

時間復雜度

不斷地將數組一分為二，直到只剩下一個元素為止，時間復雜度為 logn；
將 tmp 數組復制到 a 數組，時間復雜度為 n。
總的時間復雜度為$O(nlogn)$。

逆序對

什么是逆序對？

逆序對（Inversion）是指在一個序列中，如果前面的數比后面的數大，那么這兩個數就構成一個逆序對。

逆序對和排序的關系

• 逆序對的數量衡量了序列的無序程度：逆序對越多，序列越亂；逆序對越少，序列越接近有序。
• 排序的本質就是消除逆序對

例題

P1908 逆序對

分析

首先我們可以想到兩層for循環暴力統計逆序對個數，但是會超時。

我們可以嘗試一下分治的思想，在原數組中找逆序對，相當于先將數組一分為二，在左半邊數組找逆序對，在右半邊數組找逆序對，再一左一右找逆序對，所有的逆序對數量加起來就是原數組的逆序對數量。

于是我們得到了這樣兩個數組，分別對左右求逆序對，這咋求？？？這還不是要兩層for循環挨個遍歷統計逆序對嗎，這算上二分數組的時間復雜度，現在總時間復雜度干到了$O(n^{2}logn)$，這能對嗎？

但是當左邊這個數組和右邊這個數組分別有序的時候，再統計逆序對個數就非常方便了。我們選擇一個元素在左邊數組，另一個元素在右邊數組的逆序對，統計邏輯如下：

我們可以發現，這與歸并排序中合并有序數組的流程是一致的。

但是這里就有一個問題：對左邊數組和右邊數組分別排序的話，是否會影響逆序對的統計呢？
不會，因為在統計一左一右的時候，左右數組的逆序對已經統計過了，才形成的左右這樣有序的數組，統計逆序對的統計和歸并排序是同時進行的。
我們仍可以從極限情況分析，當數組的長度為2時，分成左右數組，它們的長度分別為1，于是左右數組中的逆序對個數肯定為0，我們接下來統計一左一右的逆序對個數，統計完之后，這個長度為2的數組也就通過歸并排序變得有序了。另一邊肯定也通過這樣相同的流程得到了一個長度為2的有序數組，然后對它們進行一左一右的逆序對統計，這時候再思考為什么不分別統計左右數組中的逆序對個數呢？因為已經統計過了，它們就是在一左一右合并的過程中統計的。

代碼

#include<iostream>using namespace std; typedef long long LL;const int N = 5e5 + 10;int n, a[N], tmp[N];LL merge(int left, int right)
{if(left >= right) return 0;//1.一分為二int mid = (left + right) >> 1; //2.計算左右數組LL ret = 0; ret += merge(left, mid);ret += merge(mid + 1, right);//3.合并左右數組int cur1 = left, cur2 = mid + 1, i = left;while(cur1 <= mid && cur2 <= right){if(a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];else{tmp[i++] = a[cur2++];ret += mid - cur1 + 1; }	} while(cur1 <= mid) tmp[i++] = a[cur1++];while(cur2 <= right) tmp[i++] = a[cur2++];for(int j=left;j<=right;j++) a[j] = tmp[j];return ret;
}int main()
{cin >> n;for(int i=1;i<=n;i++) cin >> a[i];cout << merge(1,n) << endl;	return 0;
}