题目：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
思路：
1、顺序扫描
顺序扫描整个数组，每扫描到一个数字，就将该数字跟后面的数字比较，如果大于的话，则这两个数字构成了逆序对。（比较简单，这里就不贴出代码）
时间复杂度：O(n^2)
2、归并思想
将数组不断地等分为两个子数组，然后自下而上地统计两个子数组各自的逆序对以及合并后的逆序对。
假设两个子数组左右分别为A，B，长度分为lenA,lenB，子数组已排好序，那么如何计算逆序对的个数呢？
当pA=lenA-1；pB=lenB-1；A[pA]>A[pB]，说明A的最后一个数比B所有的数都大，此时个数为lenB，pA--；如果A[pA]<B[pB]，说明左边的数不一定比右边的大，pB--；依次计算直至pA或pB为0，这样就得到了两个数组合并时的逆序对，再加上左子数组的逆序对和右子数组的逆序对，就等于整个数组的逆序对。
（代码中巧妙地利用了一个辅助数组来排序，参考下面的代码）
时间复杂度：O(nlogn)
代码：
#include <iostream>
using namespace std;
int InversePairsCore(int *data,int *copy,int start,int end){
if(start==end){
copy[start]=data[start];
return 0;
}
int length=(end-start)>>1;
int left=InversePairsCore(copy,data,start,start+length);
int right=InversePairsCore(copy,data,start+length+1,end);
int i=start+length;
int j=end;
int copyIndex=end;
int count=0;
while(i>=start && j>=start+length+1){
if(data[i]>data[j]){
copy[copyIndex]=data[i];
copyIndex--;
i--;
count+=j-(start+length);
}
else{
copy[copyIndex]=data[j];
copyIndex--;
j--;
}
}
for(;i>=start;i--)
copy[copyIndex--]=data[i];
for(;j>=start+length+1;j--)
copy[copyIndex--]=data[j];
return left+right+count;
}
int InversePairs(int *data,int length){
if(data==NULL || length<=0)
return 0;
int* copy=new int[length];
for(int i=0;i<length;i++)
copy[i]=data[i];
int count=InversePairsCore(data,copy,0,length-1);
delete[] copy;
return count;
}
int main()
{
int A[]={7,5,6,4};
int length=sizeof(A)/sizeof(A[0]);
cout << InversePairs(A,length) << endl;
return 0;
}
在线测试OJ：
http://www.nowcoder.com/books/coding-interviews/96bd6684e04a44eb80e6a68efc0ec6c5?rp=2
AC代码：
class Solution {
public:
int InversePairs(vector<int> data) {
int length=data.size();
if(length<=1)
return 0;
int start=0;
int end=length-1;
int result=InversePairsCore(data,start,end);
return result;
}
int InversePairsCore(vector<int> &data,int start,int end){
if(start>=end)
return 0;
int mid=start+((end-start)>>1);
int left=InversePairsCore(data,start,mid);
int right=InversePairsCore(data,mid+1,end);
int i=start;
int j=mid+1;
int count=0;
vector<int> tmp;
while(i<=mid && j<=end){
if(data[i]>data[j]){
count+=end-j+1;
tmp.push_back(data[i]);
i++;
}
else{
tmp.push_back(data[j]);
j++;
}
}
while(i<=mid)
tmp.push_back(data[i++]);
while(j<=end)
tmp.push_back(data[j++]);
for(int k=start;k<=end;k++)
data[k]=tmp[k-start];
return left+count+right;
}
};
class Solution {
public:
int InversePairs(vector<int> data) {
int length=data.size();
if(length<=0)
return 0;
vector<int> copy(data.begin(),data.end());
int start=0;
int end=length-1;
int count=InversePairsCore(data,copy,start,end);
return count;
}
int InversePairsCore(vector<int> &data,vector<int> ©,int start,int end){
if(start==end){
copy[start]=data[start];
return 0;
}
int length=(end-start)>>1;
int left=InversePairsCore(copy,data,start,start+length);
int right=InversePairsCore(copy,data,start+length+1,end);
int i=start+length;
int j=end;
int copyIndex=end;
int count=0;
while(i>=start && j>=start+length+1){
if(data[i]>data[j]){
copy[copyIndex--]=data[i--];
count+=j-(start+length);
}
else
copy[copyIndex--]=data[j--];
}
for(;i>=start;i--)
copy[copyIndex--]=data[i];
for(;j>=start+length+1;j--)
copy[copyIndex--]=data[j];
return left+count+right;
}
};