使用归并排序来计算逆序数
2023-06-13 09:14:14 时间
计算逆序数
在很早之前,我曾经发过一篇文章,讲的是冒泡排序的交换次数就是逆序数。可是,这样计算逆序数的话,时间成本就很高,比较冒泡是时间复杂度为O(N²)的算法呢!那怎么办呢?其实,我们可以使用归并排序的思想来计算逆序数。
(以下内容需要先了解归并排序,具体讲解可以看我的这一篇文章:)
我们会发现,在进行升序的归并排序时,每一次后方元素移到前面来的移动距离就是本次操作的逆序数。那么我们思考之后可以得出,每一步操作的逆序数就是n1-i
具体得看下面这个图:
由于每一层递归结束之后,左右两边都变成了已经升序排序的数组,那么自然地,当右边的元素小于左边元素的时候,把它移到前面的逆序数就是n1-i
代码实现
#include<iostream>
using namespace std;
unsigned int L[100002],R[100002];
unsigned int num[200002];
unsigned long long nixushu=0;
void _Merge(int left, int mid, int right)
{
int n1 = mid-left;
int n2 = right-mid;
for(int i=0;i<n1;i++)
L[i] = num[left+i];
for(int i=0;i<n2;i++)
R[i] = num[mid+i];
L[n1]=R[n2]=1000000003;
int js1=0,js2=0;
for(int i=left;i<right;i++)
{
if(L[js1]<=R[js2])
{
num[i] = L[js1];
js1++;
}
else
{
num[i] = R[js2];
js2++;
nixushu += n1-js1;
}
}
}
void mergeSort(int left, int right)
{
if(left+1>=right)
return;
int mid = (left+right)/2;
mergeSort(left,mid);
mergeSort(mid,right);
_Merge(left, mid, right);
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>num[i];
mergeSort(0,n);
cout<<nixushu<<endl;
}
因此,我们需要关注的关键问题就是合并函数的实现。经过上面的分析,我们可以知道,我们只需要在归并排序的合并函数里面,负责处理L[js1]>R[js2]的那部分代码里面做一些修改,就可以实现计算逆序数的目的。
相关文章
- pytorch BatchNorm参数详解,计算过程
- 计算任意的四则运算算式
- R语言怎么计算两个比值的 p 值?
- 驱动开发:内核LDE64引擎计算汇编长度
- OpenCV计算图像的梯度特征
- 2023年关键的云计算和安全趋势
- 快速入门pandas进行数据挖掘数据分析[多维度排序、数据筛选、分组计算、透视表](一)
- 常用排序算法的时间和空间复杂度及算法时间复杂度的简单计算详解程序员
- 掌握Oracle字段运算技巧,快速完成计算(oracle字段运算)
- Hibernate max方法:计算某一列的最大值
- 函数利用Oracle中的Max函数实现最大值计算(oracle的max)
- 硬核观察 #331 阿里巴巴使用量子计算来保护支付宝的金融交易
- 云计算与 OpenStack – 每天5分钟玩转 OpenStack(14)
- 增强边缘计算的安全性
- 如何抓住正在爆发的边缘计算市场机遇? | 英特尔AI百佳创新激励计划
- Linux操作系统:让计算变得更简单(linux的操作系统)
- 利用Oracle计算求和的方法(oracle中怎么列求和)
- Oracle V 表空间优化计算空间效率(oracle v表空间)
- Redis统计网站UV新技术的使用(redis 计算uv)
- 「FDA常客」Aidoc与Imbio合作,对疑似肺栓塞进行优先排序,并自动计算RV/LV比值