归并排序——逆序数对的统计

逆序数对的统计

题目描述

运行代码

#include <iostream>
using namespace std;
#define LL long long 
const int N = 1e5 + 5;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r)
{if (l >= r)return 0;  int mid = l + r >> 1;  LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);    int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else{res += mid - i + 1;tmp[k ++ ] = q[j ++ ];}while (i <= mid)tmp[k ++ ] = q[i ++ ];while (j <= r)tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ )q[i] = tmp[j];  return res;
}
int main()
{int n;scanf("%d", &n);for (int i = 0; i < n; i ++ ) 
scanf("%d", &a[i]);    cout << merge_sort(a, 0, n - 1) << endl;  return 0;
}

代码思路

宏定义与常量

  • #define LL long long:定义LLlong long类型的别名,用于存储较大的整数,例如逆序对的数量。
  • const int N = 1e5 + 5;:定义数组的最大容量,适用于最多100,005个元素的数组。

函数merge_sort此函数递归地将数组分成更小的部分,然后合并这些部分,同时计算逆序对总数。

  • 参数q[]是要排序的数组,lr分别是当前子数组的左右边界(索引)。
  • 基础情况:当左边界大于等于右边界时(即子数组只有一个或没有元素),返回0,表示该子数组没有逆序对。
  • 分解:计算中间索引mid,递归地对左右两部分[l, mid][mid+1, r]进行排序并计算逆序对,将结果累加到res中。
  • 合并
    • 初始化辅助数组tmp和三个指针k, i, j。当i未超过midj未超过r时,比较q[i]q[j]的大小:
      • 如果q[i] <= q[j],说明当前元素不会形成新的逆序对,将q[i]放入tmp,并移动ik
      • 否则,所有q[i]q[mid]之间的元素都比q[j]大,因此增加了mid - i + 1个逆序对,将q[j]放入tmp,移动jk
    • 分别处理剩余的元素,将它们依次放入tmp。将tmp中的元素复制回原数组q
  • 返回值:最终返回整个数组排序过程中的逆序对总数res
  • 主函数main读取数组长度n。通过循环读取数组a中的每个元素。调用merge_sort函数,传入数组a和其边界(0和n-1),输出计算得到的逆序对总数。

改进思路

  • 使用指针直接操作数组:在mergeSortAndCount函数中,直接使用指针ijk而非索引,这在某些情况下可以略微提高访问效率。
  • 保持数组作为参数:继续使用原生数组作为函数参数,保持与原始代码结构的一致性。
  • 代码格式和可读性:调整代码格式,确保良好的可读性和一致性,比如增加必要的空格和换行。
  • 去除不必要的类型别名:保留int64_t作为长整型的别名,因为它清晰地表达了数据类型的目的。

改进代码

#include <iostream>
using namespace std;
typedef long long int64_t;
// 使用指针代替数组索引来优化访问速度
int64_t mergeSortAndCount(int a[], int temp[], int left, int right) {if (left >= right) return 0;   int mid = left + (right - left) / 2;   // 递归排序并计数int64_t inv_count = mergeSortAndCount(a, temp, left, mid);inv_count += mergeSortAndCount(a, temp, mid + 1, right);   // 合并阶段计算逆序对int i = left, j = mid + 1, k = left;while (i <= mid && j <= right) {if (a[i] <= a[j]) {temp[k++] = a[i++];} else {inv_count += mid - i + 1;temp[k++] = a[j++];}}  // 复制剩余元素while (i <= mid) temp[k++] = a[i++];while (j <= right) temp[k++] = a[j++];    // 将排序结果复制回原数组for (int p = left; p <= right; ++p) a[p] = temp[p];   return inv_count;
}
int main() {const int N = 1e5 + 10;int a[N], temp[N];int n;scanf("%d", &n);   for (int i = 0; i < n; ++i) scanf("%d", &a[i]);   int64_t inv_count = mergeSortAndCount(a, temp, 0, n - 1);cout << inv_count << endl;   return 0;
}

其他方法(使用向量) AI生成

#include <iostream>
#include <vector>using namespace std;
using int64_t = long long;// 合并排序并计数逆序对
int64_t mergeSortAndCount(vector<int>& array, vector<int>& temp, int left, int right) {if (left >= right) return 0;int mid = left + (right - left) / 2;// 递归排序左右两边,并计算逆序对int64_t inv_count = mergeSortAndCount(array, temp, left, mid);inv_count += mergeSortAndCount(array, temp, mid + 1, right);// 合并阶段计算逆序对int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {if (array[i] <= array[j]) {temp[k++] = array[i++];} else {inv_count += mid - i + 1; // 计算逆序对temp[k++] = array[j++];}}// 处理剩余元素while (i <= mid) temp[k++] = array[i++];while (j <= right) temp[k++] = array[j++];// 将排序结果复制回原数组copy(temp.begin(), temp.begin() + k, array.begin() + left);return inv_count;
}int main() {int n;cin >> n;vector<int> a(n);for (int& elem : a) cin >> elem;vector<int> temp(n); // 临时数组用于合并cout << mergeSortAndCount(a, temp, 0, n - 1) << endl;return 0;
}
  1. 添加函数注释:解释每个函数的作用,特别是merge_sort中的逻辑。
  2. 使用更明确的变量名:如将q[]改为array[],使代码意图更清晰。
  3. 去除全局变量:尽量减少全局变量的使用,改用函数参数传递。
  4. 优化类型别名的可读性:将LL改为更明确的别名,如typedef long long int64_t;
  5. 使用C++风格的输入输出:完全替换scanfprintfcincout

归并、插入和冒泡排序比较

归并排序

  • 优点:时间复杂度在平均和最坏情况下都为 ,性能比较稳定,适合大规模数据排序。
  • 缺点:需要额外的空间用于合并。

插入排序

  • 优点:对于接近有序的数据表现非常好,在小规模数据或部分有序数据上效率可能较高,代码简单。
  • 缺点:最坏情况时间复杂度为 。

冒泡排序

  • 优点:实现简单。
  • 缺点:时间复杂度较差,也是 。

一般来说,在数据规模较大且对性能要求较高时,归并排序通常表现更好。但如果数据规模较小或者数据有一定的特殊性(如接近有序),插入排序可能更合适。而冒泡排序相对来说在大多数情况下效率较低,较少被优先选用。

使用归并排序解决逆序数对统计问题思路:

在归并排序的合并过程中,当我们比较左右两部分元素时,左边部分一个较大元素如果出现在右边部分较小元素之前,那么就构成一个逆序数对。

当左边当前元素大于右边当前元素时,由于左右两边都是已排序的,那么左边该元素之后的所有元素与右边当前元素都构成逆序数对,数量为左边当前未处理元素的数量。我们可以在合并的同时统计这样的逆序数对数量。通过递归地执行归并排序,不断在合并过程中累加逆序数对的数量,最终就能得到总的逆序数对数量。

例如,假设有数组 [3, 1, 4, 2],在第一次合并 [3] 和 [1] 时,因为 3 大于 1,此时就找到一个逆序数对,然后继续递归合并其他部分并统计。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/345683.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OPPO高级项目经理曹帆受邀为第十三届中国PMO大会演讲嘉宾

全国PMO专业人士年度盛会 OPPO互联网服务系统内容生态中心高级互联网项目经理曹帆先生受邀为PMO评论主办的2024第十三届中国PMO大会演讲嘉宾&#xff0c;演讲议题为“加、减、乘、除——激活项目团队效能”。大会将于6月29-30日在北京举办&#xff0c;敬请关注&#xff01; 议…

初中英语优秀作文分析-004My favorite Chinese traditional story-我最喜欢的中国传统故事

PDF格式公众号回复关键字:SHCZYF004 记忆树 1 There are many traditional stories in China. 翻译 中国有很多传统故事 简化记忆 传统故事 句子结构 There be句型 many traditional stories 名词短语 很多传统故事&#xff0c;in China 介词短语&#xff0c;在中国 …

Docker:利用Docker搭建一个nginx服务

文章目录 搭建一个nginx服务认识nginx服务Web服务器反向代理服务器高性能特点 安装nginx启动nginx停止nginx查找nginx镜像拉取nginx镜像&#xff0c;启动nginx站点其他方式拉取nginx镜像信息通过 DIGEST 拉取镜像 搭建一个nginx服务 首先先认识一下nginx服务&#xff1a; NGI…

【Linux】进程6——环境变量

1.什么是环境变量 环境变量(environment variables)一般是指在操作系统中用来指定操作系统运行环境的一些参数 比如&#xff1a;我们在编写C/C代码的时候&#xff0c;在链接的时候&#xff0c;从来不知道我们的所链接的动态静态库在哪里&#xff0c;但是照样可以链接成功&…

什么是档案数字化管理

档案数字化管理指的是将传统的纸质档案转换为数字形式&#xff0c;并通过电子设备、软件和网络技术进行管理和存储的过程。 档案数字化管理包括以下几个步骤&#xff1a; 1. 扫描和数字化&#xff1a;将纸质档案通过扫描仪转换为数字图像或文档。可以使用OCR&#xff08;光学字…

使用C++结合OpenCV进行图像处理与分类

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的在读研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三…

Java 期末复习 习题集

&#x1f496; 单选题 &#x1f496; 填空题 &#x1f496; 判断题 &#x1f496; 程序阅读题 1. 读代码写结果 class A {int m 5;void zengA(int x){m m x;}int jianA(int y){return m - y;} }class B extends A {int m 3;int jianA(int z){return super.jianA(z) m;} …

笔记本充电出现了问题。

不知道为什么。电池充电图片一直显示的空。谁能救救我&#xff01;

[图解]建模相关的基础知识-07

1 00:00:04,710 --> 00:00:08,900 这是划分&#xff0c;下一个是有序对的概念 2 00:00:11,720 --> 00:00:13,800 我们知道集合是不分顺序的 3 00:00:15,090 --> 00:00:18,200 我们花括号来代表集合的话 4 00:00:18,210 --> 00:00:21,000 AB花括号等于BA花括号 …

【python报错】关于 xlrd.biffh.XLRDError: Excel xlsx file; not supported 解决方法【已解决】

【Python报错】关于xlrd.biffh.XLRDError: Excel xlsx file; not supported解决方法【已解决】 在使用Python进行数据分析时&#xff0c;经常需要处理Excel文件。xlrd库是一个流行的用于读取Excel文件的库&#xff0c;但如果你在使用xlrd打开.xlsx文件时遇到了xlrd.biffh.XLRDE…

aabb c++

题目描述 查找形如"aabb"的四位完全平方数&#xff0c;也即前两位数字相同&#xff0c;后两位数字也相同。 输入 无 输出 若干行&#xff0c;每行一个符合条件的四位数&#xff08;从小到大&#xff09;。 分析&#xff1a; 完全平方数&#xff1a; &#xff…

两款好用的IOS、Android图片处理应用

GIF 小助手 GIF工具包是一个简单实用的GIF动画编辑器&#xff0c;目前仅支持IOS平台。 使用该软件&#xff0c;可以将多个图像、视频和现场照片创建为gif。 主要功能&#xff1a; 多种输入源&#xff1a;用户可以将多个图片、视频或Livephoto转换成GIF动图。 编辑功能&#…

TalkingData 是一家专注于提供数据统计和分析解决方案的独立第三方数据智能服务平台

TalkingData 是一家专注于提供数据统计和分析解决方案的独立第三方数据智能服务平台。通过搜索结果&#xff0c;我们可以了解到 TalkingData 的一些关键特性和市场情况&#xff0c;并将其与同类型产品进行比较。 TalkingData 产品特性 数据统计与分析&#xff1a;提供专业的数…

西门子学习笔记11 - PTO脉冲指令的使用

1、使用指令前的设置 1、打开一个脉冲发生器&#xff0c;并启用 2、选择使用PTO(脉冲A和方向B) 3、硬件设置输出 4、这样前期的准备工作就完成了 2、指令的使用 1、添加指令CTRL_PTO 2、配置如下 3、方向控制程序如下 4、最后进行测试即可

大厂真实面试题(一)

滴滴大数据sql 取出累计值与1000差值最小的记录 1.题目 已知有表t_cost_detail包含id和money两列,id为自增,请累加计算money值,并求出累加值与1000差值最小的记录。 2.分析 本题主要是想找到累加值域1000差距最小的记录,也就是我们要对上述按照id进行排序并且累加,并…

DP:回文串模型

一、回文子串 . - 力扣&#xff08;LeetCode&#xff09; 该题有3种解法 &#xff08;1&#xff09;中心扩展算法&#xff08;在字符串章节有介绍&#xff09;时间复杂度O&#xff08;N^2&#xff09;,空间复杂度O&#xff08;1&#xff09; &#xff08;2&#xff09;马丁车…

GPU风扇不旋转:为什么会发生这种情况以及如何修复

GPU在处理数百万像素时往往会发热,因此冷却风扇静音可能会令人担忧,这是可以理解的!如果你注意到你的GPU风扇没有旋转,下面是如何评估是否存在真正的问题,以及如何解决问题。 风扇停止旋转可能是一个功能,而不是一个Bug 如果GPU没有用于密集任务或没有达到高温,则可以…

GEE训练教程——如何确定几何形状的中心点坐标和相交的坐标

简介 在GEE中&#xff0c;可以使用.geometry()方法来获取几何形状的中心点坐标和相交的坐标。 首先&#xff0c;使用.geometry()方法获取几何形状的几何信息&#xff0c;然后使用.centroid()方法获取几何形状的中心点坐标。示例代码如下&#xff1a; // 获取几何形状的中心点…

idea编码问题:需要 <标识符> 非法的类型 、需要为 class、interface 或 enum 问题解决

目录 问题现象 问题解决 问题现象 今天在idea 使用中遇到的一个编码的问题就是&#xff0c;出现了这个&#xff1a; Error:(357, 28) java: /home/luya...........anageService.java:357: 需要 <标识符> Error:(357, 41) java: /home/luya............anageService.ja…

QT C++ QTableWidget 表格合并 setSpan 简单例子

这里说的合并指的是单元格&#xff0c;不是表头。span的意思是跨度、宽度、范围。 setSpan函数需要设定行、列、行跨几格&#xff0c;列跨几格。 //函数原型如下 void QTableView::setSpan(int row, i nt column, 、 int rowSpanCount,/*行跨过的格数*/ int columnSpanCount…