问题描述:给定序列(a1,…,an)。请求出这个序列中逆序对的总数。 • 输入格式 • n • a1 a2 … an • 输出格式 • 一个数T,表示逆序对的个数。C语言写代码
时间: 2024-01-18 19:02:36 浏览: 54
逆序对计数用C语言求解
下面是基于归并排序的逆序对统计的 C 语言代码实现:
```c
#include <stdio.h>
int merge_sort(int arr[], int left, int right, int temp[]) {
if (left >= right) {
return 0;
}
int mid = (left + right) / 2;
int left_cnt = merge_sort(arr, left, mid, temp);
int right_cnt = merge_sort(arr, mid + 1, right, temp);
int merged_cnt = 0;
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
merged_cnt += mid - i + 1;
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int m = left; m <= right; m++) {
arr[m] = temp[m];
}
return left_cnt + right_cnt + merged_cnt;
}
int main() {
int n;
scanf("%d", &n);
int arr[n], temp[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int inv_cnt = merge_sort(arr, 0, n - 1, temp);
printf("%d\n", inv_cnt);
return 0;
}
```
该代码首先定义了一个 `merge_sort()` 函数,该函数用于排序并统计逆序对个数,函数的输入参数为数组 `arr`、左右两个指针 `left` 和 `right`,以及临时数组 `temp`,函数的返回值为逆序对的个数。在 `merge_sort()` 函数中,如果 `left` 大于等于 `right`,则直接返回 0。否则,将 `arr` 分成左右两个数组,分别调用 `merge_sort()` 函数并得到左右两个数组的逆序对个数,然后调用 `merge()` 函数将左右两个数组进行合并,并统计逆序对的个数。最后将左右两个数组的逆序对个数和合并后的逆序对个数相加并返回即可。
在 `merge()` 函数中,定义了一个 `merged_cnt` 变量用于统计逆序对的个数,同时使用三个指针 `i`、`j` 和 `k` 分别指向左右两个数组的开头和临时数组的开头,比较左右两个指针所指的元素,将较小的元素加入到 `temp` 数组中,并将对应的指针向右移动。如果右边的元素比左边的元素小,则说明右边的元素与左边剩余的所有元素都构成逆序对,将逆序对的个数加上左边剩余的元素个数即可。最后将左右两个数组剩余的元素加入到 `temp` 数组中并将 `temp` 数组的值赋回到 `arr` 数组中即可。
最后在主程序中读入输入数据,将数据传入 `merge_sort()` 函数进行处理,得到逆序对的个数并输出即可。
阅读全文