用c语言分治算法解决逆序对个数问题

在C语言中，我们可以使用分治法来解决逆序对（也称作“下降对”）的问题，这是一个经典的计算机科学问题，通常用于评估数组元素排列的混乱程度。给定一个整数数组，我们需要找到其中有多少对元素满足第一个元素大于第二个元素的条件。

一种常见的解决策略是归并排序的思想，因为归并排序过程中会自动计算出逆序对的数量。以下是简单的步骤：

1. **分割**（Divide）: 将原始数组一分为二，直到每个子数组只有一个元素。
2. **合并**（Combine）: 对两半数组进行合并，同时统计逆序对。当比较两个元素时，如果前一个元素大于后一个，就增加一个逆序对计数。
3. **合并返回**: 把合并后的结果递归地应用到剩余的子数组上。

以下是一个简化版的C语言代码示例：

#include <stdio.h>

int merge(int arr[], int l, int m, int r) {
    int i, j, k = 0;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    i = 0;
    j = 0;
    while (i < n1 && j < n2) {
        if (L[i] > R[j]) {
            arr[k++] = R[j++];
        } else {
            arr[k++] = L[i++];
        }
    }

    while (i < n1)
        arr[k++] = L[i++];

    while (j < n2)
        arr[k++] = R[j++];

    return k;
}

void countInversions(int arr[], int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    countInversions(arr, l, mid);
    countInversions(arr, mid + 1, r);

    int inversionsInLeft = countInversions(arr, l, mid);
    int inversionsInRight = countInversions(arr, mid + 1, r);

    int mergedInvCount = inversionsInLeft + inversionsInRight;
    int temp[2 * mid + 1];
    merge(arr, l, mid, r, temp);

    // 更新左半边和右半边的逆序对数
    inversionsInLeft += merge(temp, l, mid, mid, arr);
    inversionsInRight += merge(temp, mid + 1, r, 2 * mid + 1, arr);

    return inversionsInLeft + inversionsInRight;
}

int main() {
    int arr[] = {2, 4, 1, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Number of inversion pairs is %d\n", countInversions(arr, 0, n - 1));
    return 0;
}