?
归并排序
基本思想
归并排序是用分治的思想。将大问题分成许多小问题。在每层递归上有三个步骤
具体演示
将数组一分为二，直到分割到只剩一个元素的时候开始向上递归，可以发现在合并数组之前，两个子数组都是有序的
代码模板
#include
using namespace std;
const int N=1e6+10;
int tmp[N];
void merge_sort(int q[],int l,int r){
? ?//递归函数的出口。当切割到只剩一个元素的时候向上递归
? ?if(l>=r)return;
? ?//移位的优先级没有加法高，相当于(l+r)/2
? ? int mid=l+r>>1;
? ?//对左半边处理
? ?merge_sort(q,l,mid);
? ?//对右半边处理
? ?merge_sort(q,mid+1,r);
? ?//处理完成两部分数组 l-mid整体有序 mid+1到r整体有序，通过临时数组tmp对两个数组进行操作。定义一个左指针和右指针来对比元素的大小，k为tmp的长度也就是l-r的元素个数
? ?int i=l,j=mid+1,k=0;
? ?//当两个数组都有剩余元素进行循环如果左边数组小，将左边数组元素放入tmp，指针向后移动一位，数组长度k++，反之数组右边元素放入tmp，指针向后移动一位，数组长度++;
? ?while(i<=mid&&j<=r){
? ? ? ?if(q[i]<q[j])tmp[k++]=q[i++];
? ? ? ?else tmp[k++]=q[j++];
? }
? ?//如果上面的循环结束说明有一个数组已经没有的剩余元素。那么另外的数组的剩余元素的第一个一定大于tmp[k]，只需将剩余数组的元素平移到tmp即可
? ?while(i<=mid)tmp[k++]=q[i++];
? ?while(j<=r)tmp[k++]=q[j++];
? ?//对tmp进行遍历。将tmp的元素平移到目标数组的l-r
? ?for(int i=l,j=0;j<k;i++,j++){
? ? ? ?q[i]=tmp[j];
? }
}
int main(){
? ?int q[N],n;
? ?cin>>n;
? ?for(int i=0;i<n;i++)cin>>q[i];
? ?merge_sort(q,0,n-1);
? ?for(int i=0;i<n;i++)cout<<q[i]<<" ";
}
逆序对的数量
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。 逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j] ，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。 第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1
≤
n
≤
100000
，
1≤n≤100000 ，
1≤n≤100000，
数列中的元素的取值范围[1,1e9]
输入样例
6
2 3 4 5 6 1
输出样例
5
题目的意思是数组前面的数比后面的大就能构成一对逆序对[2,1],[3,1],[4,1],[5,1],[6,1]正好五对。可以是用递归的方法处理这个问题。将可能出现的逆序对抽象成三种情况
三种情况组成的逆序对相加就是数组的全部逆序对，对数组的左右两边排序，对第三种条件的计算会方便很多。例如q[L]>q[R]，那么q[L]-q[MID]就可以和q[R]组成逆序对。因为两个数组都是有序的。那么q[L]之后的元素一定都大于等于q[L]。在加上q[L]>q[R]所以L后面的元素包括L都可以和下标为R的元素构成逆序对。所以采用归并排序解决。归并的特点正好完全符合这个问题。其实具体拆解，只存在第三种情况，第二种和第一种情况是由第三种情况计算得出的。
算法模板
#include
using namespace std;
const int N=1e6+10;
int tmp[N];
//数据范围过大 使用longlong类型
long long merge_sort(int q[],int l,int r){
? ?if(l>=r) return 0;
? ?int mid=l+r>>1;
? ?//将第三种情况的值转换为第一第二种
? long long ans = merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
? ? long i=l,j=mid+1,k=0;
? ?while(i<=mid&&j<=r){
? ?
? ? ? ?if(q[i]<=q[j])tmp[k++]=q[i++];
? ? ? ?else{
? ? ? ? ? ?tmp[k++]=q[j++];
? ? ? ? ? ?//mid-i+1为i-mid的元素个数，都能与q[j]组成逆序对
? ? ? ? ? ?ans=ans+mid-i+1;
? ? ? }
? }
? ?while(i<=mid)tmp[k++]=q[i++];
? ?while(j<=r) tmp[k++]=q[j++];
? ?// for(int i=0;i<6;i++)cout<<tmp[i]<<" ";
? ?// cout<<endl;
? ?for(int i=l,j=0;j<k;j++,i++){
? ? ?
? ? ? ?q[i]=tmp[j];
}
return ans;
}
int main(){
? ? int q[N],n;
? ?cin>>n;
? ?for(int i=0;i<n;i++)cin>>q[i];
? ?long long k=merge_sort(q,0,n-1);
? ?cout<<k<<endl;
? ? ?
? return 0;
}
?