归并排序
归并排序是一种排序方式，分为两个步骤，归与并。归就是一直分组分到不能再分为止，并就是合并，（显而易见这是一个递归回溯的过程）
过程
比如说有8个数
开始阶段：10 6 7 1 3 9 4 2（对半砍）
第一次分解：10 6 7 1 3 9 4 2（对半砍）
第二次分解：10 6 7 1 3 9 4 2（对半砍）
第三次分解：10 6 7 1 3 9 4 2
合并阶段（排序）
第一次： 6 10 1 7 3 9 2 4
第二次：1 6 7 10 2 3 4 9
第三次：1 2 3 4 6 7 9 10 完成~！😋
代码实现
显然主体是个递归过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void merger_sort(long long a[],long long l,long long r)
{
if(l>=r) return;//终止条件：分到不能再分
int mid=(l+r)/2;
merger_sort(a,l,mid);//砍砍砍！
merger_sort(a,mid+1,r);//砍砍砍！
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)//合并的过程：可以理解成有i和j两堆牌，小的在上面
//比较两牌顶的牌，谁小就把谁拿出来，放到已排序序列tem[]
{
if(a[i]<=a[j])//i牌顶的牌较小
tem[k++]=a[i++];//已排序序列指针后移，i牌顶指针下移（因为已经取了牌顶的一张牌，现在应该指向新的牌顶）
else
tem[k++]=a[j++];//（同上）
}
while(i<=mid) tem[k++]=a[i++];//检验是否还有剩下的数
while(j<=r) tem[k++]=a[j++];//同上
for(int i=l,k=0;i<=r;i++,k++)
a[i]=tem[k];//将排好序的数据复制到数组
}
|
例题
7-2 逆序对的数量分数 100
全屏浏览
切换布局
作者 wzx
单位 山东科技大学
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式:
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式:
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数据不会超出int范围。
输入样例:
输出样例:
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
long long n,a[100001],tem[100001],ans=0;
void merger_sort(long long a[],long long l,long long r)
{
if(l>=r) return;
int mid=(l+r)/2;
merger_sort(a,l,mid);
merger_sort(a,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
{
tem[k++]=a[i++];
}
else
{
tem[k++]=a[j++];
ans+=(mid-i+1);//j的序号肯定在i后，此时a[i]还大于a[j]，而此时a[]已经排完了序，那序号i后的数都大于a[j],都构成逆序对
}
}
while(i<=mid) tem[k++]=a[i++];
while(j<=r) tem[k++]=a[j++];
for(int i=l,k=0;i<=r;i++,k++)
a[i]=tem[k];
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
merger_sort(a,0,n-1);
cout<<ans;
return 0;
}
|
