编辑代码

#include <stdio.h>
#include <stdlib.h>

int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);

/* 这个函数对输入数组进行排序，并返回数组中的逆序对数 */
int mergeSort(int arr[], int array_size)
{
    int* temp = (int*)malloc(sizeof(int) * array_size);
    return _mergeSort(arr, temp, 0, array_size - 1);
}

/* 递归的辅助函数，对输入数组进行排序并返回数组中的逆序对数 */
int _mergeSort(int arr[], int temp[], int left, int right)
{
    int mid, inv_count = 0;
    if (right > left) {
        /* 将数组分成两个部分，并为每个部分调用_mergeSort() */
        mid = (right + left) / 2;

        /* 逆序对数将是左侧、右侧以及合并过程中产生的逆序对的和 */
        inv_count = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid + 1, right);

        /* 合并两部分 */
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}

/* 这个函数合并两个已排序的数组，并返回数组中的逆序对数 */
int merge(int arr[], int temp[], int left, int mid, int right)
{
    int i, j, k;
    int inv_count = 0;

    i = left; /* i是左子数组的索引*/
    j = mid; /* j是右子数组的索引*/
    k = left; /* k是结果合并子数组的索引*/
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];

            /* 在这里打印逆序对 */
            for (int p = i; p <= mid - 1; p++) {
                printf("(%d, %d)\n", arr[p], arr[j - 1]);
            }

            inv_count = inv_count + (mid - i);
        }
    }

    /* 将左子数组的剩余元素复制到临时数组（如果有）*/
    while (i <= mid - 1)
        temp[k++] = arr[i++];

    /* 将右子数组的剩余元素复制到临时数组（如果有）*/
    while (j <= right)
        temp[k++] = arr[j++];

    /* 将合并的元素复制回原始数组 */
    for (i = left; i <= right; i++)
        arr[i] = temp[i];

    return inv_count;
}

/* 主函数，测试以上函数 */
int main(int argv, char** args)
{
    int arr[] = {1, 20, 6, 4, 5};
    printf(" 逆序对的数量是 %d \n", mergeSort(arr, 5));
    return 0;
}