排序模板+求逆序对（归并的思想）

快速排序模板：

void quick_sort(int l,int r){
	if(l>=r) return ;
	int i=l-1,j=r+1,tmp=a[l+r>>1];
	while(i<j){
		do j--; while(a[j]>tmp);
		do i++; while(a[i]<tmp);
		if(i<j) swap(a[i],a[j]);
		else{
			quick_sort(l,j);
			quick_sort(j+1,r);
		}
	}
} 

归并排序模板：

void merge_sort(vector<int> &q,int l,int r){
	if(l>=r)
	    return;
	int mid=(l+r)/2;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);
	static vector<int> w;
	w.clear(); 
	int i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<=q[j])
		    w.push_back(q[i++]);
		else
		    w.push_back(q[j++]);
	}
	while(i<=mid) w.push_back(q[i++]);
	while(j<=r) w.push_back(q[j++]);
	for(int i=l,j=0;j<w.size();i++,j++)
	    q[i]=w[j];
} 

求一个数组中的逆序对的个数：

这个用到了归并的原理，你需要求出左边部分的逆序对数，然后求出右边部分的逆序对数，然后还要求出左半部分和右半部分汇总起来的时候的逆序对数

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
int find(vector<int> &q,int l,int r){
	if(l>=r)
	    return 0;
	int res=0;
	int mid=(l+r)/2;
	res+=find(q,l,mid);//左 
	res+=find(q,mid+1,r);//右 
	static vector<int> w;
	w.clear(); 
	int i=l,j=mid+1;
	while(i<=mid&&j<=r){//交叉排序 
		if(q[i]<=q[j])
		    w.push_back(q[i++]);
		else{
			res+=mid-i+1;//!!! p[j] 比 p[i] 小的时候，一定也比后边的都小 
			w.push_back(q[j++]);
		}
	}
	while(i<=mid) w.push_back(q[i++]);//剩余部分 
	while(j<=r) w.push_back(q[j++]);
	for(int i=l,j=0;j<w.size();i++,j++)
	    q[i]=w[j];
	return res;
} 
int main(){
    vector<int> a;
    int x;
    for(int i=0;i<5;i++){
    	cin>>x;
    	a.push_back(x);
	}
	cout<<find(a,0,a.size()-1);
	return 0;
}