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 生日广州男生祝福语简短