欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序求逆序对

程序员文章站 2022-05-10 15:33:18
...

昨天Noip初赛里考到了这个内容。我人品不错猜到了题。逆序对的定义是:在一个数组中,选择两个数(一共有C n 2种选法),这么多选法里前者比后者大的对数即为逆序对的个数,也就是进行冒泡排序时两两交换的次数。直接进行冒泡排序固然可以,可是复杂度很大,跟不上100000的数据量。所以我们要用NlogN的方法求逆序对。我知道的方法有两种,一种是线段树,我不会;还有一种就是比较好写的归并排序法。归并排序是怎么做的呢?把数组分成两半,对每一半排序,然后合并的时候,从第一个数开始用两个指针i和j扫,如果前者比后者大,在把后者放到tmp数组里的时候想一想,要想把后者变到前面去,你要交换mid-i+1个数字。是不是这样?所以代码实现如下。以下是暴力压过行的。

#include<bits/stdc++.h>
using namespace std;
const int boss=1e5;
int a[boss+10],s,tmp[boss+10];
void mergesort(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1,i,j,p;
mergesort(l,mid),mergesort(mid+1,r);
for (i=l,j=mid+1,p=l;i<=mid&&j<=r;a[i]>a[j]?tmp[p++]=a[j++],s+=mid-i+1:tmp[p++]=a[i++]);
while (i<=mid) tmp[p++]=a[i++];
while (j<=r) tmp[p++]=a[j++];
for (i=l;i<=r;i++) a[i]=tmp[i]; 
}
int main()
{
for (int n,i;scanf("%d",&n)==1;s=0)
  {
  for (i=1;i<=n;i++) scanf("%d",&a[i]);
  mergesort(1,n);
  for (i=1;i<=n;i++) printf("%d ",a[i]);     
  printf("\n%d\n",s);
  }
}

我写一个不压行的。

#include<bits/stdc++.h>
using namespace std;
const int boss=1e5;
int a[boss+10],s,tmp[boss+10];
void mergesort(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1,i=l,j=mid+1,p=l;
mergesort(l,mid),mergesort(mid+1,r);//对左边一半排序,对右边一半排序
while (i<=mid&&j<=r)//以下合并过程
  if (a[i]>a[j])
    {
    s+=mid-i+1;//逆序对增加
    tmp[p]=a[j];//把a[j]放到tmp里
    p++;
    j++;
    }
  else 
    {
    tmp[p]=a[i];
    p++;
    i++;
    }
while (i<=mid)//这两个while是让两个一半中剩下的数字加到tmp数组里
  {
  tmp[p]=a[i];
  p++;
  i++;
  }
while (j<=r)
  {
  tmp[p]=a[j];
  p++;
  j++;
  }
for (i=l;i<=r;i++) a[i]=tmp[i];//合并回去 
}
int main()
{
for (int n,i;scanf("%d",&n)==1;s=0)
  {
  for (i=1;i<=n;i++) scanf("%d",&a[i]);
  mergesort(1,n);
  for (i=1;i<=n;i++) printf("%d ",a[i]);     
  printf("\n%d\n",s);
  }
}