归并排序同时计算逆序对数

归并排序同时求逆序对数

c++11：

#include <iostream>
#include <algorithm>
#include <vector>
#include <initializer_list>
using namespace std;

vector<int> v({5,4,3,2,7,6});
int reverse_pairs=0;
void merge(vector<int> &v, int start, int step, vector<int> &temp){
	const int n=v.size();
	int s1=start;
	int e1=start+step;
	int s2=e1;
	int e2= s2+step<n ? s2+step : n;
	int i=start;
	while(s1<e1&&s2<e2){
		if(v[s1]<=v[s2]){
			temp[i]=v[s1];
			--step;//复用step，用于计算逆序数
			++s1;
		}
		else{
			temp[i]=v[s2];
			reverse_pairs+=step;
			++s2;
		}
		++i;
	}
	if(s1<e1){
		copy(v.begin()+s1,v.begin()+e1,temp.begin()+i);
	}
	if(s2<e2){
		copy(v.begin()+s2,v.begin()+e2,temp.begin()+i);
	}
}
void msort(vector<int> &v){
	reverse_pairs=0;
	const int n=v.size();
	vector<int> temp(n); //临时空间
	int step=1;
	for(;step<n;step*=2){
		int i=0;
		for(;i<n-step;i+=2*step){
			merge(v,i,step,temp);
		}
		if(i<n)
			copy(v.begin()+i, v.end(), temp.begin()+i);
		swap(v,temp);
	}
}

int main() {
	for_each(v.begin(),v.end(),[&](int & x){cout<<x<<"  ";});
	cout<<endl<<endl;
	
	msort(v);
	
	cout<<reverse_pairs<<endl;
	for(int x: v){
		cout<<x<<"  ";
	}
	cout<<endl;
}

object Main extends App {
	var reverse_pairs=0  //逆序数
	def msort[T](cmp:(T,T)=>Boolean)(l:List[T]):List[T]={
		def merge(l1:List[T],l2:List[T]):List[T] = (l1,l2) match{
				case(Nil,_) => l2
				case(_,Nil) => l1
				case(x::left1,y::left2) => 
				if(cmp(x,y))
					x::merge(left1,l2)  
				else{
					reverse_pairs+=l1.length  //增加逆序数
					y::merge(l1,left2)
				}
		}
		val n=l.length/2
		if(n==0)
			return l
		else{
			val (l1,l2)=l.splitAt(n)
			merge(msort(cmp)(l1),msort(cmp)(l2))
		}
	}
	println(msort((x:Int,y:Int)=>x<y)(List(5,4,3,2,7,6)))
	println(reverse_pairs)
}

最后

以上就是激动夕阳为你收集整理的归并排序同时计算逆序对数的全部内容，希望文章能够帮你解决归并排序同时计算逆序对数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。