C语言实现，分治算法，数组A【0，...，n-1】是一个n个不同整数数构成的数组。如果i<j,但是A[i]〉A[j]，则这对元素（A[i]，A[j]）被称为一个倒置（inversion）。设计一个O（nlogn）算法来计算数组中的倒置数量 【输入形式】输入两行，第一行输入元素的个数n，第二行输入n个数据（中间用一个空格隔开）； 【输出形式】输出一个整数，即逆置数的个数；

分治算法是一种将问题分解为子问题然后递归求解的算法。对于这道题，我们可以使用分治算法来解决。

具体思路是：将数组A分成两个子数组，分别计算出左右子数组中的逆置数，然后再计算跨越左右子数组的逆置数。最后将三者之和相加即可得到整个数组的逆置数。

代码如下：

#include <stdio.h>

int merge(int A[], int left, int mid, int right)
{
    int i, j, k;
    int count = 0;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = A[left + i];
    for (j = 0; j < n2; j++)
        R[j] = A[mid + 1 + j];
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        }
        else {
            A[k] = R[j];
            j++;
            count += (n1 - i);
        }
        k++;
    }
    while (i < n1) {
        A[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        A[k] = R[j];
        j++;
        k++;
    }
    return count;
}

int mergeSort(int A[], int left, int right)
{
    int mid, count = 0;
    if (left < right) {
        mid = (left + right) / 2;
        count += mergeSort(A, left, mid);
        count += mergeSort(A, mid + 1, right);
        count += merge(A, left, mid, right);
    }
    return count;
}

int main()
{
    int n, i;
    scanf("%d", &n);
    int A[n];
    for (i = 0; i < n; i++)
        scanf("%d", &A[i]);
    int count = mergeSort(A, 0, n - 1);
    printf("%d", count);
    return 0;
}

在主函数中，首先输入数组元素的个数n和n个数据，然后调用mergeSort函数计算逆置数，并输出结果。

mergeSort函数是一个递归函数，用于将数组分成左右两个子数组，并分别计算出左右子数组的逆置数。最后还要计算跨越左右子数组的逆置数，并将三者之和返回。

merge函数用于计算跨越左右子数组的逆置数。具体做法是，将左右两个子数组合并成一个有序数组，并在合并的过程中计算逆置数。如果左边的元素大于右边的元素，则说明存在逆置，此时将逆置数加上左子数组剩余的元素个数（因为左子数组已经有序，所以左子数组剩余的所有元素都大于右子数组的当前元素）。