2:求排列的逆序数 查看 提交 统计 提问 总时间限制:
1000ms
内存限制:
65536kB
描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。
对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。
现给定1,2,…,n的一个排列，求它的逆序数。
输入
第一行是一个整数n，表示该排列有n个数（n <= 100000)。 第二行是n个不同的正整数，之间以空格隔开，表示该排列。
输出
输出该排列的逆序数。
样例输入
6 2 6 3 4 5 1 样例输出
8 直接二重循环计算的复杂度是，注意到如果前后分成两段是排好序的，那么逆序数，依次可以计算出所有逆序数，为
mid - p1+1，这就是算法的核心
实现归并排序归并的时候，需要辅助的空间，最后在将辅助空间排序好的结果复制给原数组，在函数中传入辅助数组是为了节省空间。另外为了简单，逆序数答案直接用全局变量输出了
#include #define N 100010 using namespace std; long long ans; void Merge(int a[], int s, int m, int e,int temp[]) { //将数组a的局部a[s,m]和a[m+1，e]合并到temp，保证temp有序 int pb = 0; int p1 = s; int p2 = m + 1; while (p1 <= m && p2 <= e) { if (a[p1] < a[p2]) { temp[pb++] = a[p1++]; } else { ans += m - p1 + 1; temp[pb++] = a[p2++];
} } while (p1 <= m) { temp[pb++] = a[p1++]; } while (p2 <= e) { temp[pb++] = a[p2++]; } for (int i = 0; i < e - s + 1; i++) { a[s + i] = temp[i]; }}
void MergeSort(int a[], int s, int e, int temp[]) { // s为a开始下标，e为结束的下标 if (s < e) { int m = s + (e - s) / 2; MergeSort(a, s, m, temp); MergeSort(a, m + 1, e, temp); Merge(a, s, m, e, temp); }
}
int main() { int size; int a[N]; int b[N]; scanf_s("%d", &size); for (int i = 0; i < size; i++) { scanf_s("%d", &a[i]); }
MergeSort(a, 0, size - 1, b); /*for (int i = 0; i < size; i++) { cout << a[i] << " "; } cout << endl;*/ cout << ans << endl; return 0;}
归并排序的直观写法，关键在于合并两个数组的过程
#include<stdio.h> void merge(int a[], int first, int middle, int last, int temp[]) { int i = first, j = middle + 1, k = 0; int l; while (i <= middle && j <= last) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } if (i == middle + 1) { for (l = j; l <= last; l++) { temp[k++] = a[l]; } } if (j == last + 1) { for (l = i; l <= middle; l++) { temp[k++] = a[l]; } } for (l = 0; l < last - first + 1; l++) { a[first + l] = temp[l]; }
}
void mergeSort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = first + (last - first) / 2; mergeSort(a, first, mid, temp); mergeSort(a, mid+1, last, temp); merge(a, first, mid, last, temp); } } int main() { int a[10] = { 9,8,7,6,5,4,3,2,1 }; int b[10]; mergeSort(a, 0, 8, b); for (int i = 0; i < 9; i++) printf("%d ", a[i]);
} ———————————————— 版权声明：本文为博主「wwxy261」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/wwxy1995/article/details/82953957
