帮我用C语言求倒置数 【问题描述】数组A【0,...,n-1】是一个n个不同整数数构成的数组。如果i<j,但是A[i]〉A[j],则这对元素(A[i],A[j])被称为一个倒置(inversion)。设计一个O(nlogn)算法来计算数组中的倒置数量 【输入形式】输入两行,第一行输入元素的个数n,第二行输入n个数据(中间用一个空格隔开); 【输出形式】输出一个整数,即逆置数的个数; 【样例输入1】 8 2 3 8 9 1 4 5 7 【样例输出1】 10 【样例输入2】 2 21 7 【样例输出2】 1
时间: 2023-11-28 09:51:11 浏览: 73
以下是使用归并排序求解倒置数的C语言代码:
```c
#include <stdio.h>
long long merge(int a[], int l, int mid, int r) {
int i = l, j = mid + 1, k = 0;
int tmp[r - l + 1];
long long cnt = 0;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
cnt += mid - i + 1; // 统计逆序对
tmp[k++] = a[j++];
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (i = l, k = 0; i <= r; i++, k++) {
a[i] = tmp[k];
}
return cnt;
}
long long merge_sort(int a[], int l, int r) {
if (l >= r) return 0;
int mid = (l + r) / 2;
long long cnt = 0;
cnt += merge_sort(a, l, mid);
cnt += merge_sort(a, mid + 1, r);
cnt += merge(a, l, mid, r);
return cnt;
}
int main() {
int n, i;
scanf("%d", &n);
int a[n];
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
long long ans = merge_sort(a, 0, n - 1);
printf("%lld\n", ans);
return 0;
}
```
首先,定义 `merge` 函数用来合并两个有序数组,并在合并过程中统计逆序对的数量。具体来说,我们用两个指针 `i` 和 `j` 分别指向左半部分和右半部分的起始位置,比较 `a[i]` 和 `a[j]` 的大小,将小的数存入临时数组 `tmp`,并将对应的指针后移一位。如果 `a[i] > a[j]`,那么说明左半部分从 `i` 到 `mid` 这些数都大于 `a[j]`,因此可以统计逆序对的数量为 `mid - i + 1`。最后将剩余的数存入 `tmp` 中,并将 `tmp` 中的数复制回原数组 `a` 中。
然后,定义 `merge_sort` 函数用来归并排序,并在排序过程中统计逆序对的数量。如果左右指针相等或者左指针大于右指针,说明该部分只有一个数或者没有数,不需要排序,直接返回0。否则,将该部分分成左右两个部分,分别递归调用 `merge_sort` 函数,得到左半部分和右半部分的逆序对数量。然后,调用 `merge` 函数合并左右两个部分,并将得到的逆序对数量累加到总的逆序对数量中。
最后,在 `main` 函数中读入数组,并调用 `merge_sort` 函数求解逆序对数量,输出即可。
阅读全文