HzuQZH

用户名：h1810819001

访问量：32318

签　名：

等　　级
排　　名	45
经　　验	12276
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

数据结构-KMP字符串模式匹配算法实现-题解(C++代码)
浏览：504

数据结构-用数组实现堆排（易处理，容易理解）
浏览：634

区间dp（动归思想）
浏览：938

你可能喜欢

逆序对——归并排序算法，易懂！！

　　作者: HzuQZH　　　　发表时间：2019-11-02 10:21:57 浏览：798　|　评论：0　

原题链接：逆序数

# 前治知识点：[归并排序](https://blog.csdn.net/weixin_43738764/article/details/102842500)

### 逆序对：在一个序列中，存在一个前面的数大于后面的数就成为逆序对（如2 1 4 3 中，2 1、4 3）

**用归并排序处理逆序对的时间复杂度:O(nlogn)**

大致上于归并排序的模板类似，但主要的差别在于：因为归并排序分为的是左右两个区间进行处理。
	所以，当左区间i所指向的元素大于右区间j指向的元素时，i与i之后的元素都与j所指向的元素成为逆序对。

如这样一个数组：
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191102101443945.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczODc2NA==,size_16,color_FFFFFF,t_70)
	
	经过递归排序后
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191102101505413.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczODc2NA==,size_16,color_FFFFFF,t_70)

## 如上所说：当左区间的当前元素大于右区间的当前元素时，左区间元素与之后的元素都与右区间当前元素可以组成一个逆序对

上代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> Pall;
namespace IO{
    inline LL read(){
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
const int N=1e6+7,INF=0x3f3f3f3f;
int a[N];
LL merge_sort(int l,int r){//
    if(l>=r)return 0;
    int mid=l+r>>1;
    LL res=merge_sort(l,mid)+merge_sort(mid+1,r);
    int i=l,j=mid+1,temp[r-l+1],cnt=0;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j])temp[cnt++]=a[i++];
        //其他地方如果不同，可以转移到归并排序链接。
        else{//如果i指向左区间的元素大于右区间j指向的元素
            res+=mid-i+1;//那么i之后的元素都能与j组成一对逆序对
            temp[cnt++]=a[j++];
        }
    }
    while(i<=mid)temp[cnt++]=a[i++];
    while(j<=r)temp[cnt++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++)a[i]=temp[j];
    return res;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    cout<<merge_sort(0,n-1)<<endl;
    return 0;
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

HzuQZH

TA的其他文章

你可能喜欢

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【数组的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

校门外的树（C语言代码）

逆序对——归并排序算法，易懂！！

评论区

精彩推荐

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

【简单计算】（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

sizeof的大作用（C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

矩形面积交（C++代码）

2^k进制数（C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

数列问题（C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

HzuQZH

TA的其他文章

你可能喜欢

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【数组的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

校门外的树 （C语言代码）

逆序对——归并排序算法，易懂！！

评论区

精彩推荐

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

【简单计算】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

sizeof的大作用 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

矩形面积交 （C++代码）

2^k进制数 （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

数列问题 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言训练-大、小写问题（C语言代码）

【数组的距离】（C语言代码）

校门外的树（C语言代码）

　　评论区

【简单计算】（C语言代码）

sizeof的大作用（C语言代码）

矩形面积交（C++代码）

2^k进制数（C语言描述，蓝桥杯）

数列问题（C语言代码）