三种方法求逆序数(暴力、归并排序、树状数组+离散化) Apare_xzc

三种方法求逆序数(暴力、归并排序、树状数组+离散化)

Apare_xzc

2021.3.20

先挂一张今日讲课画的图：

直接上代码吧…

可读性还是可以的

/**
* Author: xzc
* 2021.3.20 21:30
*/
#include <bits/stdc++.h>
using namespace std;

namespace BstRev {  // 树状数组求逆序数 
	int lowbit(int x) {
		return x & (-x);
	}
	void update(vector<int>& c, int x, int val, int n) {
		while(x <= n) {
			c[x] += val;
			x += lowbit(x);
		}
	}
	int getSum(vector<int>& c, int x) {
		int ans = 0;
		while (x > 0) {
			ans += c[x];
			x -= lowbit(x); 
		}
		return ans;
	}
	long long getRevNum(const vector<int>& v) {
		vector<int> b = v;
		sort(b.begin(), b.end());  // 离散化
		int n = v.size();
		long long ans = 0; 
		vector<int> c(n+1, 0);
		int maxIndex = lower_bound(b.begin(), b.end(), b[n-1]) - b.begin() + 1;
		for (int i = 0; i < n; ++i) {
			int index = lower_bound(b.begin(), b.end(), v[i]) - b.begin() + 1;
			ans += getSum(c, maxIndex) - getSum(c, index);
			update(c, index, 1, n);
		}
		return ans;
	}
};

namespace BubbleSortRev { // 暴力求逆序数 
	long long getRevNum(const vector<int>& v) {
		int n = v.size();
		long long ans = 0;
		for(int i = 1; i < n; ++i) {
			for (int j = 0; j < i; ++j) {
				if (v[j] > v[i]) {
					++ans;
				}
			}
		}
		return ans;
	}	
};

//给你一个数列(排列 1~n)  5 3 2 4 1
//逆序数：求每个数左边有几个比它大，求这些个数的和
// 1 + 2 + 1 + 4 = 8 


namespace MergeSortRev { // 归并排序求逆序数 
	long long MergeSort(vector<int>& v, int L, int R) {
		if (R - L <= 1) {
			return 0;
		}
		int mid = (L + R) / 2;
		long long ans1 = MergeSort(v, L, mid);
		long long ans2 = MergeSort(v, mid, R);
		vector<int> tmp(R-L);
		int p = 0, i = L, j = mid;
		while (i < mid || j < R) {
			if (j == R || (i < mid && v[i] <= v[j])) {
				tmp[p++] = v[i++];
			} else {
				tmp[p++] = v[j++];
				ans1 += mid - i;
			}
		} 
		p = 0;
		for (i = L; i < R; ++i) {
			v[i] = tmp[p++];
		} 
		return ans1 + ans2; 
	}
	long long getRevNum(const vector<int>& v) {
		vector<int> tmp = v;
		return MergeSort(tmp, 0, v.size());
	}	
};



int main(void) {
//	int n;
//	scanf("%d", &n);
//	int x;
//	vector<int> v;
//	for (int i = 0; i < n ; ++i) {
//		scanf("%d", &x);
//		v.push_back(x);
//	}
	srand(time(NULL));
	int n = 20;
	vector<int> v;
	int x;
	for (int i = 0; i < n; ++i) {
		x = 1ll*rand()*rand()%1000000007;
		v.push_back(x);
	}
	cout<<n<<endl;
	for (int i = 0; i < n; ++i) {
		cout<<v[i]<<" ";
	}
	cout<<endl;


	cout<<"树状数组求得数列的逆序数为："<<BstRev::getRevNum(v)<<endl;
	cout<<"冒泡排序求得数列的逆序数为："<<BubbleSortRev::getRevNum(v)<<endl;
	cout<<"归并排序求得数列的逆序数为："<<MergeSortRev::getRevNum(v)<<endl; 
	
	return 0;
}