欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【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;
}

求法3

https://blog.csdn.net/qq_37406764/article/details/81209927