c语言数组逆序数

数组逆序数指的是数组中逆序对的数量，即数组中有多少对元素，其索引位置在数组中是逆序的。以下是一个使用C语言计算数组逆序数的示例代码：

#include<stdio.h>

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

    i = left; 
    j = mid;  
    k = left; 
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
            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 mergeSort(int arr[], int temp[], int left, int right) {
    int mid, inv_count = 0;
    if (right > left) {
        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 getInvCount(int arr[], int n) {
    int temp[n];
    return mergeSort(arr, temp, 0, n - 1);
}

int main() {
    int arr[] = { 1, 20, 6, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("逆序数为 %d", getInvCount(arr, n));
    return 0;
}

运行结果为：

逆序数为 5

该算法使用了归并排序的思想，在归并排序的过程中计算逆序数。具体来说，将数组分成左右两部分，然后对左右两部分分别进行归并排序，最后将左右两部分合并成一个有序数组，并计算逆序数。逆序数等于左半部分逆序数加右半部分逆序数加左右两部分中的逆序数。