逆序对

gistfile1.txt

#include <stdio.h>
#define N 10005
int count = 0;
void Merge(int S[],int T[],int x,int m, int y)
{
    int i,j,k;
    for (i = x,j = m + 1,k = x;i <= m && j <= y; k++)
    {
        if (S[i] > S[j]) {T[k] = S[j++];count += m - i + 1;}
        else T[k] = S[i++];
    }
    while (i <= m) {T[k++] = S[i++];}
    while (j <= y) T[k++] = S[j++];
}
void MergeSort(int S[], int T[],int x, int y)
{
    int m;
    int temp[N] = {0};
    if (x == y) T[x] = S[y];
    else
    {
        m = (x + y)/2;
        MergeSort(S,temp,x,m);
        MergeSort(S,temp,m + 1,y);
        Merge(temp,T,x,m,y);
    }
}
int main()
{
    int L[N];
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
        scanf("%d",&L[i]);
    MergeSort(L,L,1,n);
    for (int i = 1; i <= n; i++) printf("%d ",L[i]);
    printf("%d",count);

    return 0;
}