编辑代码

#include <stdio.h>

// 归并函数，用于合并两个已排序的子数组并计算逆序对的数量
long long merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left;     // 左子数组的起始索引
    int j = mid + 1;  // 右子数组的起始索引
    int k = left;     // 合并后的数组的起始索引
    long long inversions = 0;  // 逆序对的数量

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            // 如果左侧元素大于右侧元素，产生逆序对
            inversions += mid - i + 1;
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }

    return inversions;
}

// 归并排序函数，同时返回逆序对的数量
long long mergeSort(int arr[], int temp[], int left, int right) {
    long long inversions = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        inversions += mergeSort(arr, temp, left, mid);
        inversions += mergeSort(arr, temp, mid + 1, right);
        inversions += merge(arr, temp, left, mid, right);
    }
    return inversions;
}

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

    int temp[n]; // 用于归并排序的临时数组
    long long inversions = mergeSort(arr, temp, 0, n - 1);

    printf("逆序对的个数: %lld\n", inversions);

    return 0;
}