C++求逆序对的方法
本文实例讲述了C++求逆序对的方法，分享给大家供大家参考之用。具体实现方法如下：
#include<iostream>
#include<vector>
usingnamespacestd;
intarray[]={3,9,7,4,5,2};
constintsize=sizeofarray/sizeof*array;
inttemp[size];
//intnumbers[size];
intreversePair(int*numbers,intstart,intlast,int&index,int&count)
{
if(start==last)
return0;
intmid=(last-start)/2+start;
reversePair(numbers,start,mid,index,count);
reversePair(numbers,mid+1,last,index,count);
for(inti=start;i<=last;i++)
temp[i]=numbers[i];
intindex1=start,index2=mid+1;
index=start;
while(index1<=mid&&index2<=last){
if(temp[index1]>temp[index2]){
numbers[index]=temp[index2];
count+=mid-index1+1;
index++;
index2++;
}elseif(temp[index1]==temp[index2]){
numbers[index]=temp[index1];
index++;
index1++;
index2++;
}elseif(temp[index1]<temp[index2]){
numbers[index]=temp[index1];
index++;
index1++;
}
}
if(index1<=mid){
while(index1<=mid){
numbers[index]=temp[index1];
index++;
index1++;
}
}else{
while(index2<=last){
numbers[index]=temp[index2];
index++;
index2++;
}
}
returncount;
}
voidmain()
{
intcount=0;
intindex=0;
reversePair(array,0,size-1,index,count);
cout<<"count="<<count<<endl;
}
希望本文所述对大家C++算法设计的学习有所帮助。