利用穷举算法求一个整数数组A中的逆序对的个数（C语言）

本文主要是介绍利用穷举算法求一个整数数组A中的逆序对的个数（C语言），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实验内容：

实验过程：

1.算法设计

2.程序清单

3.复杂度分析

4.实验结果

实验内容：

给定一个整数数组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.算法设计

基本蛮力算法：

实现countA函数，遍历数组a中所有相邻元素对(a[i],a[j])（i<j），通过双层嵌套循环实现。若a[i] > a[j]，记逆序对数count加 1。循环结束后返回count。

递归蛮力算法：

定义辅助函数 mergeB，接收已排序子数组a[left...mid]和a[mid+1...right]，统计合并过程中产生的逆序对（a[i] > a[j]），结果存回原数组。递归函数countB接收数组a及左右边界，当区间只有一个元素时返回 0；否则，递归计算左右子区间的逆序对数，调用mergeB合并子区间并累加逆序对数，返回总逆序对数。

主程序中，定义数组a及其长度n，分别调用两种方法计算逆序对数量并输出。

2.程序清单

#include <stdio.h>
//第一种方法：基本蛮力算法
int countA(int a[], int n) {int count = 0;for (int i = 0; i < n - 1; ++i) {for (int j = i + 1; j < n; ++j) {if (a[i] > a[j]) {count++;}}}return count;
}
//第二种方法：递归蛮力算法
int mergeB(int a[], int left, int mid, int right) {int i = left, j = mid, k = left, count = 0;int temp[10];while (i <=mid && j <= right) {if (a[i] <= a[j]) {temp[k++] = a[i++];} else {temp[k++] = a[j++];count++;  }}while (i<=mid) {temp[k++] = a[i++];}while (j <= right) {temp[k++] = a[j++];}//将temp数组赋值给a数组for (i = left; i <= right; i++) {a[i] = temp[i - left];}return count;
}
int countB(int a[], int left, int right) {int count = 0;if (left < right) {int mid = (left+right) / 2;count += countB(a, left, mid);count += countB(a, mid + 1, right);count += mergeB(a, left, mid+1, right);}return count;
}
int main() {int a[] = {3, 1, 4, 5, 2};int n = sizeof(a) / sizeof(a[0]);int inversions1 = countA(a, n);printf("第一种方法:暴力算法\n");printf("a中的逆序对的个数为: %d\n", inversions1);int inversions2= countB(a, 0, n - 1);printf("第二种方法:递归蛮力算法\n");printf("a中的逆序对的个数为: %d\n", inversions2);return 0;
}

3.复杂度分析

(1)时间复杂度

基本蛮力算法

时间复杂度：该方法通过两层嵌套循环遍历数组，外层循环 i 从 0 到 n-2，内层循环 j 从 i+1 到 n-1。每次比较 a[i] 和 a[j]，若 a[i] > a[j]，则计数器 count 增加。总共有 C(n, 2) = n*(n-1)/2 对元素需要比较，故时间复杂度为 O(n^2)。

递归蛮力算法

时间复杂度：该方法采用了分治策略，类似于归并排序的思想。递归函数 countB 会将数组 a 分割成两部分，分别计算左右子数组的逆序对数量，并通过 mergeB 函数合并子数组时统计跨越左右子数组的逆序对数量。mergeB 函数的时间复杂度为 O((right-left+1))，而 countB 函数递归调用自身两次，每次处理的子问题规模大约减半。因此，整个递归过程的时间复杂度符合以下关系：

T(n) = 2*T(n/2) + O(n)

这是典型的分治算法时间复杂度形式，根据主定理，其解为 T(n) = O(n log n)。

(2)空间复杂度

基本蛮力算法

空间复杂度：该方法仅使用了若干固定大小的变量（如 count、i、j），不依赖于输入数组的大小，因此空间复杂度为 O(1)。

递归蛮力算法

空间复杂度：递归调用过程中，需要额外的空间存储递归调用栈。最坏情况下，递归深度为 log n，每层递归调用需要 O(n) 的额外空间（临时数组 temp）。因此，空间复杂度为 O(n log n)。