计算逆序对个数(归并排序)
程序员文章站
2022-05-10 11:53:05
...
解题思路:这里采用分治递归计算逆序对个数的方法。总体方法和归并排序几乎没有区别(加一个定义和一句话即可求解逆序对个数)。首先将整数段分成前后两部分,递归求解,对于元素一个在左,一个在右的逆序对,可以利用归并排序的特性,当右边更小的数s[q]被加入空间T时,左边剩余的数都可以与该数组成逆序对,因而直接将总逆序对数加上左边剩余的数即可得到结果。
问题描述:给出一组整数,若某两个整数下标i<j,而ai>aj。则这两个整数形成一个逆序对。问该组数中逆序对的个数。
#include<cstdio>
#include<iostream>
using namespace std;
int s[100];
int cnt;
void gui(int a,int b)
{
if(b-a>1)
{
int m=a+(b-a)/2;
gui(a,m); //计算a-m的逆序对并归并排序
gui(m,b); //计算m-b的逆序对并归并排序
int T[100],p=a,q=m,countn=0;
while(p<m||q<b) //只要其中任意一个未到尽头就可以继续排序
{
if(p>=m||q<b&&s[q]<s[p]) //若左边到头或左右都没到头但右边更小,则将右边加入临时空间
{
T[countn++]=s[q++];
cnt+=m-p; //计算逆序对和归并排序只差了这一步。
}
else
{
T[countn++]=s[p++];
}
}
for(int i=0;i<countn;i++) //临时空间T复制到原始空间s
{
s[a+i]=T[i];
}
}
}
int main()
{
int n;
while(cin>>n)
{
cnt=0;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
gui(0,n);
for(int i=0;i<n;i++)
{
cout<<s[i]<<" ";
}
cout<<endl;
cout<<cnt<<endl;
}
return 0;
}
推荐阅读
-
python3利用归并算法对超过内存限制的超大文件进行排序
-
PHP使用array_multisort对多个数组或多维数组进行排序
-
数组中的逆序对(归并排序思想)
-
剑指Offer51.归并排序的应用之一——逆序对
-
分治法 —— 求逆序对个数 (归并排序应用2)
-
方法{【对任意个数的字符串去重排序】
-
求逆序对 ----归并排 & 树状数组
-
跟着专注于计算机视觉的AndyJ的妈妈我学算法之每日一题不是leetcode题每次移动一个数字排序
-
2018暑假多校赛【第二场】【归并排序】【逆序数】-Swaps and Inversions-YZHHHHHHH
-
树状数组 POJ2299&HDU6318 逆序对 离散化树状数组&归并排序