给定一个整数数组A=（a0,a1,…,an-1），若i<j且ai>aj，则<ai,aj>就为一个逆序对，例如数组（3,1,4,5,2）的逆序对有<3,1>,<3,2>,<4,2>,<5,2>。分别使用蛮力法和分治法设计完整的C语言代码，求A中的逆序对的个数。

蛮力法：

#include <stdio.h>

int main()
{
    int A[] = {3, 1, 4, 5, 2};
    int n = sizeof(A) / sizeof(int);
    int cnt = 0;

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (A[i] > A[j])
            {
                cnt++;
                printf("<%d, %d>\n", A[i], A[j]);
            }
        }
    }

    printf("cnt = %d\n", cnt);

    return 0;
}

分治法：

#include <stdio.h>

void merge(int A[], int l, int m, int r, int *cnt)
{
    int i = l, j = m + 1, k = 0;
    int tmp[r - l + 1];

    while (i <= m && j <= r)
    {
        if (A[i] <= A[j])
        {
            tmp[k++] = A[i++];
        }
        else
        {
            tmp[k++] = A[j++];
            *cnt += m - i + 1; // 统计逆序对个数
        }
    }

    while (i <= m)
    {
        tmp[k++] = A[i++];
    }

    while (j <= r)
    {
        tmp[k++] = A[j++];
    }

    for (int p = 0; p < k; p++)
    {
        A[l + p] = tmp[p];
    }
}

void merge_sort(int A[], int l, int r, int *cnt)
{
    if (l < r)
    {
        int m = (l + r) / 2;
        merge_sort(A, l, m, cnt);
        merge_sort(A, m + 1, r, cnt);
        merge(A, l, m, r, cnt);
    }
}

int main()
{
    int A[] = {3, 1, 4, 5, 2};
    int n = sizeof(A) / sizeof(int);
    int cnt = 0;

    merge_sort(A, 0, n - 1, &cnt);

    printf("cnt = %d\n", cnt);

    return 0;
}