编辑代码

#include <stdio.h>

int merge(int arr[], int temp[], int left, int mid, int right) 
{
    int i, j, k;
    int count = 0;
    i = left; // 左半部分的数组起始位置
    j = mid + 1; // 右半部分的数组起始位置
    k = left; // 临时数组的起始位置
    
    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 (i = left; i <= right; i++) 
    {
        arr[i] = temp[i];
    }
    
    return count;
}

int mergeSort(int arr[], int temp[], int left, int right) 
{
   
    if (left < right) // 当数组长度大于1时，继续分割
    {
        int count = 0;
        int mid = (left + right) / 2;
        count += mergeSort(arr, temp, left, mid); // 左半部分数组的逆序对数量
        count += mergeSort(arr, temp, mid + 1, right); // 右半部分数组的逆序对数量
        count += merge(arr, temp, left, mid, right); // 合并左右两部分数组，并统计逆序对数量
        return count;
    }
   return 0;
}

int main() 
{
    int arr[] = {2, 4, 3, 1, 5, 6 };
    int n = sizeof(arr) / sizeof(int);
    int temp[n]; // 临时数组
    int count = mergeSort(arr, temp, 0, n - 1); // 统计逆序对数量
    printf("逆序对数量: %d\n", count);

    int arr1[] = {20, 23, 11, 5, 21, 56};
    int n1 = sizeof(arr1) / sizeof(int);
    int temp1[n1]; // 临时数组
    int count1 = mergeSort(arr1, temp1, 0, n1 - 1); // 统计逆序对数量
    printf("逆序对数量: %d\n", count1);
}