.逆序对简介

\;\;\;\;\;\;\;\;简单介绍一下归并排序的原理，逆序对的基本概念，然后收集相关的练习。

直接用一个基础问题来引入。

因此知道了:
\;\;\;\;\;\;\;\;逆序对就是一对数满足 $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.区间的个数原题