c语言求逆序数

求逆序数可以使用归并排序的思想，在归并排序的过程中统计逆序数的个数。

具体实现如下：

#include <stdio.h>

// 归并排序并计算逆序数
int merge_sort(int arr[], int left, int right) {
    int count = 0;
    if (left < right) {
        int mid = (left + right) / 2;
        count += merge_sort(arr, left, mid); // 统计左半部分的逆序数
        count += merge_sort(arr, mid + 1, right); // 统计右半部分的逆序数
        int i = left, j = mid + 1, k = 0;
        int temp[right - left + 1];
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j])
                temp[k++] = arr[i++];
            else {
                temp[k++] = arr[j++];
                count += mid - i + 1; // 统计跨越两个区间的逆序数
            }
        }
        while (i <= mid)
            temp[k++] = arr[i++];
        while (j <= right)
            temp[k++] = arr[j++];
        for (int m = 0; m < k; m++)
            arr[left + m] = temp[m];
    }
    return count;
}

int main() {
    int arr[] = {4, 3, 1, 2, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    int count = merge_sort(arr, 0, len - 1);
    printf("逆序数的个数为：%d\n", count);
    return 0;
}

运行结果：

逆序数的个数为：7

在归并排序的过程中，如果左半部分的元素大于右半部分的元素，则说明存在逆序对，因为左半部分是已排好序的，所以左半部分剩余的元素也都大于右半部分的当前元素，所以也都与它构成逆序对。因此，在统计逆序数的时候，我们只需要在归并排序的过程中统计跨越两个区间的逆序数即可。