归并排序——求逆序对
程序员文章站
2022-05-10 15:05:26
...
//归并排序及求逆序对
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int a[N],b[N]; //b为辅助数组
long long cnt;
void merge_sort(int l,int m, int r)
{
int mid = m ;
int i = l; //辅助数组的下标
int p = l, q = mid+1;
//printf("%d-%d %d-%d\n",p,mid ,q ,r);
while(p<=mid || q<=r)//左右两部分只要有一部分不为空
{
if(q>r || (p<=mid && a[p]<=a[q]))
{//从左半数组复制到辅助数组
b[i++] = a[p++];
}
else
{
b[i++] = a[q++];
cnt += mid -p +1;//将逆序对的个数累加起来
}
}
for(i = l ;i <= r;i++)//将b中排好序的元素复制到a中
a[i] = b[i];
}
void Merge(int l,int r)
{
if(l < r)
{
int m = (l + r) >> 1;
Merge(l,m);
Merge(m+1,r);
merge_sort(l,m,r);
}
}
int main()
{
int n;
while(cin >> n)
{
for(int i = 1 ; i <= n; i ++)
cin >> a[i];
cnt = 0;
Merge(1, n);
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
printf("逆序对有:%d\n",cnt);
}
return 0;
}