C语言逆序对计数与输出详解279

逆序对 (Inversion) 是一个重要的算法概念，它指的是在一个序列中，如果存在一对元素 (a[i], a[j]) 满足 i < j 且 a[i] > a[j]，那么 (a[i], a[j]) 就构成一个逆序对。 计算逆序对的数量以及输出逆序对本身，在算法竞赛和实际应用中都有着广泛的应用，例如判断数组的排序程度、分析算法效率等等。本文将详细介绍如何在C语言中高效地计算逆序对的数量，并输出所有的逆序对。

一、暴力法 (Brute Force)

最直观的做法是暴力枚举所有可能的元素对，检查它们是否构成逆序对。这种方法的时间复杂度为 O(n^2)，其中 n 是序列的长度。对于较小的序列，这种方法足够使用，但对于大型序列，其效率极低。以下是用C语言实现的暴力法代码：```c
#include
void printInversions(int arr[], int n) {
int count = 0;
printf("逆序对：");
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
printf("(%d, %d) ", arr[i], arr[j]);
count++;
}
}
}
printf("逆序对总数：%d", count);
}
int main() {
int arr[] = {5, 3, 8, 1, 9, 2, 4, 7, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printInversions(arr, n);
return 0;
}
```

这段代码首先遍历数组中的所有元素对，然后判断是否构成逆序对。如果构成逆序对，则将其打印出来，并更新逆序对计数器。最后，输出逆序对的总数。

二、归并排序法 (Merge Sort)

归并排序是一种基于分治策略的排序算法，其时间复杂度为 O(n log n)。在归并排序的过程中，我们可以巧妙地计算逆序对的数量。当我们将两个已排序的子数组合并成一个有序数组时，如果来自左子数组的元素大于来自右子数组的元素，那么它们之间就构成了逆序对。我们可以利用这个特性来高效地计算逆序对的数量。```c
#include
void merge(int arr[], int temp[], int left, int mid, int right, long long *count) {
int i = left, j = mid + 1, k = left;
while (i

2025-04-04

上一篇：C语言printf函数详解：格式化输出的艺术

下一篇：C语言实现面积计算函数：详解与示例