归并排序 MergeSort

逆序对数

时间限制：1 秒 空间限制：65536 KB
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

Input
第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）

Output
输出逆序数

Input 示例
 4
2
4
3
1

Output 示例
4

从后往前比较，前面的数每大于后面的数一次加1，但是直接计算会超时。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[50005];
int main()
{
    int n,sum=0;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    for(int i=n-1; i>0; i--)
        for(int j=0; j<i; j++)
        if(a[j]>a[i])
          sum++;
        printf("%d\n",sum);
    return 0;
}

于是就有了 归并排序算法：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide
and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述：

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

时间复杂度为O(nlogn)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[50005],b[50005];
int mergeSort(int low,int high)
{
    if (low == high)
        return 0;
    int count=0;
    int mid=(low+high)/2;
    count = mergeSort(low,mid)+mergeSort(mid+1,high);
    int i=low,j=mid+1,k=low;
    while(i<=mid && j<=high)
        if(a[i]<=a[j])
            b[k++]=a[i++];
        else
        {
           b[k++]=a[j++];
           count += (mid - i + 1);
        }
    while(i<=mid)
        b[k++]=a[i++];
    while(j<=high)
        b[k++]=a[j++];
    for(i=low; i<=high; i++)
        a[i]=b[i];
    return count;
}
int main()
{
    int N,i;
    scanf("%d", &N);
    for (i = 0; i < N; ++i)
        scanf("%d", &a[i]);
    cout<<mergeSort(0,N-1);
    return 0;
}