归并排序求逆序对

· · 个人记录

设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。 如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数

归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。

在合并的过程中（设l<=i<=mid，mid+1<=j<=h）：

当a[i]<=a[j]时，并不产生逆序数；

当a[i]>a[j]时，在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。

因此，可以在归并排序中的合并过程中计算逆序数

具体步骤

利用分治思想，每一层递归上有三个步骤：

分解（Divide）：将n个元素分成个含n/2个元素的子序列。

解决（Conquer）：用合并排序法对两个子序列递归的排序。

合并（Combine）：合并两个已排序的子序列已得到排序结果。

例题

在这个问题中，您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列，直到序列按升序排序。

对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

输入格式

输入包括一些测试用例。

每个测试用例的第一行输入整数 n，代表该用例中输入序列的长度。

接下来 n 行每行输入一个整数 ai,代表用例中输入序列的具体数据，第 i 行的数据代表序列中第 i 个数。

当输入用例中包含的输入序列长度为 0 时，输入终止，该序列无需处理。

输出格式

对于每个需要处理的输入序列，输出一个整数 op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。

数据范围

0≤n<500000,

一个测试点中，所有 n 的和不超过 500000。

0≤ai≤999999999

输入样例：

5
9
1
0
5
4
3
1
2
3
0

输出样例：

6
0

分析：

发现题目在模拟冒泡排序，而交换的次数，就是冒泡排序的交换次数就是我们的逆序对个数，至于求逆序对最快的方法，就是归并排序。

实现代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
ll a[N],b[N];
ll cnt;
void find(ll a[],ll l,ll r)
{
    if(r-l<1)
    return;
    ll mid=(l+r)>>1;
    find(a,l,mid);
    find(a,mid+1,r);
    ll i=l,j=mid+1;
    for(ll k=l;k<=r;k++)
    {
        if(j>r||i<=mid&&a[i]<=a[j])
        b[k]=a[i++];
        else
        b[k]=a[j++],cnt+=mid-i+1;
    }
    for(ll k=l;k<=r;k++)
    a[k]=b[k];
}
int main()
{
    ll n;
    while(cin>>n)
    {
        if(!n)
        return 0;
        cnt=0;
        for(ll i=1;i<=n;i++)
        cin>>a[i];
        find(a,1,n);
        cout<<cnt<<endl;
    }
}