# 前言

✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第七讲：排序【例/习题】

💖有关快速排序模板见博文：快速排序算法模板

💖有关归并排序模板见博文：归并排序算法模板

👊归并排序

👊逆序对的数量

# 归并排序

1≤n≤100000

5

3 1 2 4 5

1 2 3 4 5

## 代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N], backup[N];
void merge_sort(int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
{
if (a[i] < a[j]) backup[k ++ ] = a[i ++ ];
else backup[k ++ ] = a[j ++ ];
}
while (i <= mid) backup[k ++ ] = a[i ++ ];
while (j <= r) backup[k ++ ] = a[j ++ ];
for (int i = l, j = 0; i <= r; i ++, j ++ )
a[i] = backup[j];
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
merge_sort(1, n);
for (int i = 1; i <= n; i ++ )
printf("%d ", a[i]);
return 0;
}

# 逆序对的数量

6

2 3 4 5 6 1

5

## 思路分析

1. 左子区间上的两个数构成逆序对
2. 右子区间上的两个数构成逆序对
3. 左字区间的一个数和右子区间的一个数构成逆序对

res = merge_sort(l, mid) + merge_sort(mid + 1, r);

## 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N], backup[N];
LL res;
LL merge_sort(int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
res = (LL)merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
{
if (a[i] <= a[j]) backup[k ++ ] = a[i ++ ];
else   //因为j肯定是大于i的,所以证明此时是一个逆序对
{
backup[k ++ ] = a[j ++ ];
res += mid - i + 1;
}
}
while (i <= mid) backup[k ++ ] = a[i ++ ];
while (j <= r) backup[k ++ ] = a[j ++ ];
for (int i = l, j = 0; i <= r; i ++, j ++ )
a[i] = backup[j];
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
printf("%lld\n", merge_sort(1, n));
return 0;
}

|
2月前
|

23 0
|
3月前

24 0
|
3月前
|

30 0
|
3月前
|

19 0
|
3月前
|

②【Java 组】蓝桥杯省赛真题解析 [振兴中华] [三部排序] 持续更新中...
②【Java 组】蓝桥杯省赛真题解析 [振兴中华] [三部排序] 持续更新中...
36 0
|
3月前
|

32 0
|
10月前
|

[蓝桥杯] 二分与前缀和习题练习

84 0
|
10月前
|

[蓝桥杯] 递归与递推习题训练

60 0
|
10月前
|

36 0
|
10月前
|

66 0