1311:【例2.5】求逆序对 归并排序

2023-12-14 12:57:26

1311:【例2.5】求逆序对
【题目描述】
给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目。

【输入】
第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。

【输出】
所有逆序对总数

【输入样例】
4
3
2
3
2
【输出样例】
3
【提示】
N≤105,Ai≤105

注意:

  • 逆序数的可以考虑是排序过程时大数在前小数在后的比较次数,如果数组比较大则不能考虑冒泡、选择、插入(时间复杂度很高)

  • 逆序数由于在递归排序时是中间偏后一位的数和之前的作比较,比较时只要第一位比它大则剩下的左序列都比他大,所以逆序数一次可求多个(冒泡一次交换只能得到一个逆序数对): num+=mid-i+1
    在这里插入图片描述

  • 由于数组比较大时,逆序数这个值可能很大,需要数据类型为long long
    代码:

#include <bits/stdc++.h>
using namespace std;
const int Max  = 100011;
int a[Max],r[Max];
long long num=0; 
void merge_sort(int s,int t);
int main(){
	int len;
	cin>>len;
	for(int i=0;i<len;i++){
		cin>>a[i];
	}
	merge_sort(0,len-1);
	cout<<num;
	return 0;
} 
void merge_sort(int s,int t){
	if(s==t) return ;
	int mid = (s+t)/2;
	merge_sort(s,mid);//先完成左边的排序 
	merge_sort(mid+1,t);//先再完成右边的排序 
	int i=s,j=mid+1,k=s;//开始合并序列 
	while(i<=mid&&j<=t){//将数据放到临时数组里面,判断的左边的序列右边子序列的第一个(即mid+1)
		if(a[i]<=a[j]){  //判断是否该值小于右边子序列的第一个值
			r[k]=a[i];
			k++,i++;
		}else{
			r[k]=a[j]; //否则较小的值就移到临时数组K
			num+=mid-i+1;
			k++,j++;
		}
	}
	while(i<=mid){ //复制左边的剩下序列过去 
		r[k]=a[i];
		k++,i++;
	} 
	while(j<=t){ //复制右边的序列 
		r[k]=a[j];
		k++,j++;
	}
	for(int i=s;i<=t;i++){
		a[i]=r[i];  //将此次排序的数据放回数组中
		cout<<a[i]<<" ";
	}
	cout<<endl;
}

文章来源:https://blog.csdn.net/m0_46183615/article/details/134990884
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。