归并排序 MergeSort
2023-03-14 10:17:24 时间
逆序对数 时间限制:1 秒 空间限制:65536 KB 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。 如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。给出一个整数序列,求该序列的逆序数。 Input 第1行:N,N为序列的长度(n <= 50000) 第2 - N + 1行:序列中的元素(0 <= A[i] <= 10^9) Output 输出逆序数 Input 示例 4 2 4 3 1 Output 示例 4从后往前比较,前面的数每大于后面的数一次加1,但是直接计算会超时。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[50005]; int main() { int n,sum=0; scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d",&a[i]); for(int i=n-1; i>0; i--) for(int j=0; j<i; j++) if(a[j]>a[i]) sum++; printf("%d\n",sum); return 0; }于是就有了 归并排序算法:
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
算法描述:
归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
时间复杂度为O(nlogn)
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[50005],b[50005]; int mergeSort(int low,int high) { if (low == high) return 0; int count=0; int mid=(low+high)/2; count = mergeSort(low,mid)+mergeSort(mid+1,high); int i=low,j=mid+1,k=low; while(i<=mid && j<=high) if(a[i]<=a[j]) b[k++]=a[i++]; else { b[k++]=a[j++]; count += (mid - i + 1); } while(i<=mid) b[k++]=a[i++]; while(j<=high) b[k++]=a[j++]; for(i=low; i<=high; i++) a[i]=b[i]; return count; } int main() { int N,i; scanf("%d", &N); for (i = 0; i < N; ++i) scanf("%d", &a[i]); cout<<mergeSort(0,N-1); return 0; }
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的