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++算法设计的学习有所帮助。
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短