【ACM入门】逆序数
程序员文章站
2022-05-22 10:19:20
...
什么是逆序数
对于数列A,如果存在一组数(Ai, Aj),满足Ai > Aj 且 i < j 呢么这是一个逆序。
求法1
根据冒泡排序的相邻比较大小交换的规则,可知冒泡排序元素的交换次数就是该序列的逆序数,(代码),时间复杂度O(n^2)
int bubble_sort(int arr[], int len) {
int i, j, cnt;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
cnt ++;
}
return cnt;
}
求法2利用归并排序
归并排序
思路:
1.分割数组(一分为二)。
2.分别对分割的左右数组进行并归排序。
3.合并两个数组进行排序。
#include <iostream>
using namespace std;
#define MAX 50000
#define SENTINEL 2000000000
int L[MAX / 2 + 2], R[MAX / 2 + 2];
int cnt;
//合并数组
void merge(int A[], int n, int left, int mid, int right) {
int n1 = mid - left;
int n2 = right - mid;
for ( int i = 0; i < n1; i++ ) L[i] = A[left + 1];
for ( int i = 0; i < n2; i++ ) R[i] = A[mid + 1];
L[n1] = R[n2] = SENTINEL;
int i = 0, j = 0;
for ( int k = left; k < right; k++ ) {
cnt++; //记录执行了多少次比较
if ( L[i] <= R[j] ) {//小的先进入A
A[k] = L[i++];
} else {
A[k] = R[j++];
}
}
}
//并归排序
void mergeSort(int A[], int n, int left, int right) {
if ( left + 1 < right ) {
int mid = (left + right) / 2; //找分割位置
// 左右并轨然后合并
mergeSort(A, n, left, mid);
mergeSort(A, n, mid, right);
merge(A, n, left, mid, right);
}
}
int main(void) {
int A[MAX], n, i;
cnt = 0;
cin >> n;
for (i = 0; i < n; i++) cin >> A[i];
mergeSort(A, n, 0, n);
for (i = 0; i < n; i++) {
if ( i ) cout << " ";
cout << A[i];
}
cout << endl;
cout << cnt << endl;
return 0;
}
利用并归的思想,每次找L和R数组中满足,L[i] > R[i]的个数,并进行累加。
#include <iostream>
using namespace std;
#define MAX 50000
#define SENTINEL 2000000000 //一个超大的数
int L[MAX / 2 + 2], R[MAX / 2 + 2];
int cnt;
//合并数组
int merge(int A[], int n, int left, int mid, int right) {
int n1 = mid - left; //L数组的长度
int n2 = right - mid; //R数组的长度
for ( int i = 0; i < n1; i++ ) L[i] = A[left + 1];
for ( int i = 0; i < n2; i++ ) R[i] = A[mid + 1];
L[n1] = R[n2] = SENTINEL;
int i = 0, j = 0; //分别记录inL 和 R数组中 剩余数
for ( int k = left; k < right; k++ ) {
if ( L[i] <= R[j] ) {//小的先进入A
A[k] = L[i++];
} else {
A[k] = R[j++];
cnt += n1 - i; //找L和R数组中满足,L[i] > R[i]的个数,并进行累加
}
}
return cnt;
}
//并归排序
int mergeSort(int A[], int n, int left, int right) {
int v1, v2, v3;
if ( left + 1 < right ) {
int mid = (left + right) / 2;
// 左右并归然后合并
v1 = mergeSort(A, n, left, mid);
v2 = mergeSort(A, n, mid, right);
v3 = merge(A, n, left, mid, right);
return v1 + v2 + v3;
}
}
int main(void) {
int A[MAX], n, i;
cnt = 0;
cin >> n;
for (i = 0; i < n; i++) cin >> A[i];
int ans = mergeSort(A, n, 0, n);
cout << ans << endl;
return 0;
}