逆序对的数量（归并排序）

给定一个长度为?n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第?i个和第?j个元素，如果满足?i<j?且?a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数?n，表示数列的长度。

第二行包含?n个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤1000001≤100000，
数列中的元素的取值范围?[1,109][1,109]。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

?这里要注意归并排序是一种思维方法，而不仅仅是一种排序的方法。

首先，拿到这道题，具体的思维方法是：

因为归并排序只要小的数=字在大的数字后面，就得通过两两交换换两个数字的位置。所以可以用归并排序的方法来做这道题。

普通的暴力方法：

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int q[100010];
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    int num=0;
    int j;
    for(i=0;i<n-1;i++)
    {
        for(j=i;j<n;j++){
        	if(q[i]>q[j]){
        		num++;
			}
		}
    }
    printf("%d",num);
    return 0;
}

时间复杂度为n*n运行时间较长，可能不符合题目要求

归并排序方法：

#include <iostream>

using namespace std;

typedef long long LL;  //提前把long long数据类型简写为LL，更方便后面代码的书写

const int N = 1e5 + 10;

int a[N], tmp[N];

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;

    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);//res所表示的就是交换顺序的次数

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;  //只要前面半部分的其中一个数字x比后面板部分序列的数字大，呢么前面部分x后面的所有数都要和后面部分那个位置的数交换一下位置
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    cout << merge_sort(a, 0, n - 1) << endl;

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39791/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。