编辑代码

#include <stdio.h>

int merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;
    int inversions = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // 如果arr[i] > arr[j]，那么arr[i]到arr[mid]之间的元素都与arr[j]构成逆序对
            inversions += (mid - i + 1);
            temp[k++] = arr[j++];
        }
    }

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

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

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

    return inversions;
}

int mergeSort(int arr[], int temp[], int left, int right) {
    int inversions = 0;

    if (left < right) {
        int mid = (left + right) / 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 n;
    // printf("请输入整数的个数: ");
    // scanf("%d", &n);

    // if (n <= 0) {
    //     printf("无效的输入。\n");
    //     return 1;
    // }

    // int arr[n];
    // int temp[n];

    // printf("请输入%d个整数, 以空格隔开: ", n);
    // for (int i = 0; i < n; i++) {
    //     scanf("%d", &arr[i]);
    // }
    int arr[]={4,3,9,15,87,7};
    int inversions = mergeSort(arr, 6, 0, 5);

    printf("逆序对数目为: %d\n", inversions);

    return 0;
}