前治知识点:归并排序

逆序对:在一个序列中,存在一个前面的数大于后面的数就成为逆序对(如2 1 4 3 中,2 1、4 3)

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

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

如这样一个数组:
在这里插入图片描述

  1. 经过递归排序后

在这里插入图片描述

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

上代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. typedef pair<int,int> Pall;
  5. namespace IO{
  6. inline LL read(){
  7. LL o=0,f=1;char c=getchar();
  8. while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
  9. while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
  10. return o*f;
  11. }
  12. }using namespace IO;
  13. const int N=1e6+7,INF=0x3f3f3f3f;
  14. int a[N];
  15. LL merge_sort(int l,int r){//
  16. if(l>=r)return 0;
  17. int mid=l+r>>1;
  18. LL res=merge_sort(l,mid)+merge_sort(mid+1,r);
  19. int i=l,j=mid+1,temp[r-l+1],cnt=0;
  20. while(i<=mid&&j<=r){
  21. if(a[i]<=a[j])temp[cnt++]=a[i++];
  22. //其他地方如果不同,可以转移到归并排序链接。
  23. else{//如果i指向左区间的元素大于右区间j指向的元素
  24. res+=mid-i+1;//那么i之后的元素都能与j组成一对逆序对
  25. temp[cnt++]=a[j++];
  26. }
  27. }
  28. while(i<=mid)temp[cnt++]=a[i++];
  29. while(j<=r)temp[cnt++]=a[j++];
  30. for(i=l,j=0;i<=r;i++,j++)a[i]=temp[j];
  31. return res;
  32. }
  33. int main(){
  34. int n;
  35. cin>>n;
  36. for(int i=0;i<n;i++)cin>>a[i];
  37. cout<<merge_sort(0,n-1)<<endl;
  38. return 0;
  39. }
点赞(0)
 

9.9 分

0 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论