前言：
本篇讲归并排序的应用——求解无序序列中逆序对的数目。如果需要了解归并排序本身，请跳转至我的另一篇文章归并排序图文详解（一篇讲透归并排序）-CSDN博客。
题目
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000
数列中的元素的取值范围 [1,109][1,109]。
输入样例：
6 2 3 4 5 6 1
输出样例：
5
题目分析：
1、理解逆序对的含义：对于数组中的两个数，如果下标小的数的数值却大，那么这两个数就是一组逆序对。
2、本题的要求很简单，没有其他可以分析的。我们看到题目第一眼想到的肯定是暴力解法：就是先选择第一个数，然后一一比较后面的数，如果满足逆序对要求则+1.然后选择第二个数再和后面数一一比较，如此反复。这样写的话时间复杂度会在O（n^2)。当数据量一大后运行时间会非常可怕，所以本题肯定要考虑其他的解法。
解法分析：
归并排序思想：
1、回顾一下分离奇偶数的题目，就是给一个无序序列要求实现调整后，序列左边为奇数右边为偶数。本题我们采用的办法就是双指针，一个从左边向右走，一个从右边向左走，如果左指针遇到偶数则停止，右指针遇到奇数则停止。然后两者交换，接下来继续走直到两者相遇。这样子在运行中时刻会保持左指针左边为奇数，右指针右边为偶数的条件。
这个算法的思想和我们快速排序的核心思想是一样的。
这就说明快排和归并的核心思想很多时候能用在其他的算法当中。
2、那么归并的核心思想是什么呢？核心思想就是：采用的是双指针归并法（链表合并本质也是这样）（两两比较并合并）。我们想想这个思路能不能用在这里。
本题深入分析：
1、先上张图： 
假如我们将整个数组分为两段。那么根据这两段我们可以将逆序对分为以上三种类型，然后一一进行求解再把每种的个数相加。
逆序对1：两个数全在左边（如图中红色点）
逆序对2：两个数全在右边（如图中绿色点）
逆序对3：一个数在左边区域，另一个数在右边区域（如图中黄色的点）
2、这时再假如逆序对3，这种类似的逆序对数目能够被计算出来。那么对于左边的逆序对1和右边的逆序对2，我们就可以通过递归的方式，将左边、右边再各自划分为两个区域，计算这新的区域中的逆序对3。
3、不停分割计算逆序对3，对于1、2的计算就是通过分割花为逆序对3，以及新的逆序对1、2.直到最后一组逆序对1、2只剩一个元素，则可以知道结果，并且过程中的逆序对3一直可以计算，所以到这里问题就可以化为求解逆序对3，这一个问题。
4、求解逆序对3：让我们想想归并排序的核心思想：合并的方法采用的是双指针归并法（链表合并本质也是这样）（两两比较并合并）。
那么对于本题能不能拿来用呢？假如我们两个有序数组，我们要如何求出逆序对数？下面我通过图来说明：
选择归并原因：
1、看到这里，大家肯定能想到，这双指针，然后一个个比较大小，然后让小的那个后移的操作和归并排序一模一样啊！！所以很自然，我们可以把这两个操作合并在一起。
2、同时，我们的操作的前提正好也是两个数组内部有序。而归并排序正好也满足合并过程中内部有序的条件。
代码分析：
#include<iostream> using namespace std; int temp[100001]={0};//这个temp对于每个递归来说必须是一样的。所以在函数外面定义 long ct_inver_merge(int num[],int l,int r){ if(l>=r) return 0; int mid=(l+r)>>1; long result=0; result=ct_inver_merge(num,l,mid)+ct_inver_merge(num,mid+1,r); //先求解左边和右边的两个子区间的逆序对数目 int i=l; int j=mid+1; int k=0;//这个k对于每个递归来说都从0开始，所以必须在函数内定义 while(i<=mid&&j<=r){ if(num[i]<=num[j])temp[k++]=num[i++]; else{ temp[k++]=num[j++]; result+=mid-i+1; } //实现排序的同时计算两个有序数组间逆序对3的数目，并加到前面的result中 } while(i<=mid)temp[k++]=num[i++]; while(j<=r)temp[k++]=num[j++]; //单纯为了实现归并排序 for(int i=l,j=0;i<=r;i++,j++){ num[i]=temp[j]; } //归并排序的必要操作。求逆序对3的算法基于就是数组内部有序。 //所以实现归并保持内部有序是必须的 return result; } int main(){ int n=0; int num[100001]={0}; cin>>n; for(int i=0;i<n;i++){ cin>>num[i]; } cout<<ct_inver_merge(num,0,n-1)<<endl; }
