.逆序對簡介

\;\;\;\;\;\;\;\;簡單介紹一下歸并排序的原理，逆序對的基本概念，然后收集相關的練習。

直接用一個基礎問題來引入。

因此知道了:
\;\;\;\;\;\;\;\;逆序對就是一對數滿足 $i<j\&\&nums[i]>nums[j]$。（當然這個圖片的題目是用record存儲數字）

.歸并排序

\;\;\;\;\;\;\;\;歸并排序的時間復雜度是$O(nlo{g}^n)$，從時間復雜度上來看，和快速排序并駕齊驅，但是由于快速排序會因為基準元素導致時間復雜度有概率退化，所以嚴格來說歸并排序比快速排序是更加穩定且快的。

歸并排序的核心思想：

• 分解
• 遞歸求解（將更小的子數組排序）
• 合并 （將兩個排序后的子數組合并成一個有序數組）

通過遞歸解決子問題，最后一步步回溯解決最終的問題。

首先我會用一個示例來演示歸并排序的過程，然后計算其時間復雜度；那么歸并排序就介紹完了，后面將會持續更新題目。

有一個數組nums=[9,2,1,3,4,5,3,8,9],使用歸并排序將其從小到大排序

從底層分析，歸并排序是從下往上的，先將子數組排序后，然后合并兩個排序后的子數組。最底層就是9和2，我們認為元素是排序好的，那么將兩個排序好的子數組合并為一個大的子數組，合并這個操作就可以將這個大的子數組排序完畢。（因為兩個子數組是有序的，所以可以使用雙指針輕松排序大的數組）。

歸并排序的代碼：

void merge(vector<int>&arr,vector<int>&temp,int left,int mid,int right)
{int i = left;    // 左子數組起始指針int j = mid + 1; // 右子數組起始指針int k = left;    // 臨時數組起始指針// 比較兩個子數組元素，將較小的放入臨時數組while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 處理左子數組剩余元素while (i <= mid) {temp[k++] = arr[i++];}// 處理右子數組剩余元素while (j <= right) {temp[k++] = arr[j++];}// 將臨時數組中的元素復制回原數組for (i = left; i <= right; i++) {arr[i] = temp[i];}
}void mergeSort(vector<int>&arr,vector<int>&temp,int left,int right)
{if(left<right){int mid=(left+right)/2;//分解子問題mergeSort(arr,temp,left,mid);mergeSort(arr,temp,mid+1,right);//合并merge(arr,temp,left,mid,right);}
}

那么如何計算時間復雜度。
其實上面的圖片可以很清楚看到，每一層都要合并n次，那么一共要合并$logn$次，所以時間復雜度是$O(nlo{g}^n)$
更具體地：

T(n) = 2*T(n/2) + n                  // 第1層：將n分解為2個n/2，合并耗時n= 2*[2*T(n/4) + n/2] + n        // 第2層：2個n/2分解為4個n/4，合并總耗時2*(n/2) = n= 4*T(n/4) + 2n                 = 8*T(n/8) + 3n                 // 第k層：2^k個子數組，每個大小n/2^k，合并總耗時k*n...= n*T(1) + log2(n)*n            // 共log2(n)層，最終T(1)=O(1)

.習題

1.交易逆序對的總數 原題

2.計算右側小于當前元素的個數原題

3.翻轉對原題

4.區間的個數原題