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

归并排序——求逆序对

程序员文章站 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;
}