逆序对题解---利用归并排序解答

摘要：本文详细讲解了如何使用归并排序算法求解逆序对问题。首先介绍了归并排序的分治思想和递归实现原理，然后解释了逆序对的定义及其在归并排序合并过程中的统计方法。最后提供了完整的C++代码实现，展示了如何在归并排序过程中高效计算逆序对数量。

https://www.luogu.com.cn/problem/P1908https://www.luogu.com.cn/problem/P1908https://www.luogu.com.cn/problem/P1908

## 首先我们来讲一下归并排序

归并排序主要利用递归实现。

归并排序又叫分治法排序，那就是两个操作，分和治。

分就是将序列平均划分成两端再排序，

治就是将排好序的两部分通过比大小重新合并在一起，变成一段有序的序列。

分和治就是利用递归，粗略讲一下递归路径，一段序列先平分成两半，拿一段出来看接着平分成两段，直到最后这一段只有两个数，无法被平分了，就治，两个数比较大小排序，然后和另一部分排好序的继续比较排序，如此递归下去，最后到最开始的两大部分，因为之前已经排好序了，所以各自两段都是排好序的序列，再逐位比较，存放进数组内，此时这个 序列就是有序的序列了。

好，这时候有同学要问了，那这个归并排序那里实现了数逆序对呀？现在让我再讲一下逆序对，

逆序对 就是 位置 i < j 但是ai>aj，简而言之，就是大数在小数前面。给一个数列 问有多少对逆序对？

在归并排序中 ，我们再并的时候，也就是比较给两段有序数列排的时候，如果第一个序列的某个值大于了第二个序列的值，那么由于这些序列有序，那么第一个序列的值大于第二个序列的值，那第一个序列的这个值的后面的所有值都大于，逆序对的个数就是第一个序列这个数到这个序列的最后一个序列数的个数。

代码实现：

#include<bits/stdc++.h> using namespace std; const int N =5e5+5; int a[N],tmp[N]; long long ans; void merge_sort(int q[],int l,int r) { int mid= (l+r)/2; if(l>=r) return; merge_sort(q,l,mid); merge_sort(q,mid+1,r); int i=l,j=mid+1,k=0; while(i<=mid && j<=r) { if(q[i]>q[j]) { tmp[k++]=q[j++]; ans += mid-i+1;//逆序对的关键步骤 } else{ tmp[k++]=q[i++]; } } while(i<=mid) { tmp[k++]=q[i++]; } while(j<=r) { tmp[k++]=q[j++]; } for(int i=l,k=0;i<=r;i++,k++) { q[i]=tmp[k]; } } int main() { int n;cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } merge_sort(a,0,n-1); cout<<ans; }