给定一个整数数组 A=(a0，a1，…an-1)，若 i<j 且 ai>aj，则<ai，aj>就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有<3，1>，<3，2>，<4，2>，<5，2>。设计一个算法采用蛮力法求 A 中逆序对的个数即逆序数。设计算法求解逆序对的个数；给出c语言代码

以下是使用蛮力法求解逆序对个数的C语言代码：

#include <stdio.h>

int count_reverse_pairs(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (arr[i] > arr[j]) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 1, 4, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", count_reverse_pairs(arr, n));  // 输出 4
    return 0;
}

时间复杂度为 O(n^2)，不适用于大规模数据的处理。

相关问题

给定一个整数数组A=（a0,a1,…,an-1），若i<j且ai>aj，则<ai,aj>就为一个逆序对，例如数组（3,1,4,5,2）的逆序对有<3,1>,<3,2>,<4,2>,<5,2>。设计一个穷举算法求A中的逆序对的个数。

算法思路：
1. 枚举每一个数对（i,j），其中i<j。
2. 如果ai>aj，则逆序对个数加一。

算法实现：

def count_inversions(arr):
    n = len(arr)
    count = 0
    for i in range(n-1):
        for j in range(i+1, n):
            if arr[i] > arr[j]:
                count += 1
    return count

时间复杂度：O(n^2)，不适用于大规模数据。

给定一个整数数组A=（a0,a1,…,an-1），若i<j且ai>aj，则<ai,aj>就为逆一个序对，例如数组（3,1,4,5,2）的逆序对有<3,1>,<3,2>,<4,2>,<5,2>。设计一个c语言代码用穷举算法求A中的逆序对的个数。

#include <stdio.h>

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

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (A[i] > A[j]) {
                printf("<%d,%d>\n", A[i], A[j]);
                count++;
            }
        }
    }

    printf("逆序对个数为：%d\n", count);
    return 0;
}