数组中的逆序对（归并排序的灵活运用）

这个题目如果没有限制你的时间复杂度，那么它的在O（n²）里面完成的话，那么就很简单了。

但是如果发求你在O（n）的时间复杂度里面完成。那么这还是有点挑战性的。

题目的分析：对于逆序对的理解

先看方法：

如上面的所示，对于该算法以，我们首先将数组划分成一个一个的数字（为了排序），然后拆分成了

两个己排好序的数组。

那么如何计数逆序对呢？

如上图在（a）图中：

是两个排好序的数组，一个是5，7，另一个是4，6.

我们用两个指针P1和P2，一个指向左边那么数组的未尾，一个指向右边那么数组的未尾。

于是我们比较P1和P2所指向的这两个数，由于P1指向的数大于P2指向的数，又由于我们右

边的那个数组是从小到大排好序的，于是逆序数就是P2加它左边的数=2了。然后我们将

P1指向的数放入辅助数组中，用P3指示。P1左移一位。P2保持不动

（b）图中：

由于P1比P2小，因此此时P2指向的数无用了。因为P1应该是在左边的数组中属于最大的了

于是将P2指向的数复制到P3。然后将P2左移一位。

（C）图中：

和（a) 图相似了。

看代码：

#ifndef INVERT_DATA_COUNT_H
#define INVERT_DATA_COUNT_H
#include<iostream>
int invertPairCore(int *arr,int *copy,int start,int end); 
int invertDataPairCount(int *arr,int Length); 
int invertDataPairCount(int *arr,int Length){
	if(arr==NULL||Length==0){
		return 0; 
	}
	int *copy=new int[Length];
	/*
        for(int i=0;i<Length; i++){
		    copy[i]=arr[i]; 
	    }
    */
	int InverpairCountSum=invertPairCore(arr,copy,0,Length-1); 
	delete[] copy; 
	return InverpairCountSum;	
}
int invertPairCore(int *arr,int *copy,int start,int end){
	if(start==end){
		copy[start]=arr[start]; 
		return 0; 
	}
	int mid=(end-start)/2; //相当于归并排序，先排好序，分成两组
	int leftInvertPair=invertPairCore(arr,copy,start,start+mid); 
	int rightInvertPair=invertPairCore(arr,copy,start+mid+1,end); 
	int i=start+mid; 
	int j=end; 
	int indexCopy=end; 
	int pairCount=0; 
    //核心步骤，和图解差不多的意思。
	while(i>=start&&j>=start+mid+1){
		if(arr[i]>arr[j]){
			copy[indexCopy--]=arr[i--]; 
			pairCount+=j-(start+mid+1)+1;          
		}else{
			copy[indexCopy--]=arr[j--]; 
		}
	}
    //对剩下的数的处理，也就是在两数组比较的时候还有剩下数据拷贝到copy数组中。
	for(;i>=start; --i){
		copy[indexCopy--]=arr[i]; 
	}
	for(; j>=start+mid+1; --j){
		copy[indexCopy--]=arr[j]; 
	}
	//返回值。
    return pairCount+leftInvertPair+rightInvertPair; 
}
#endif

测试代码

#include"invertDataCount.h"
int main(){
	int arr[4]={7,5,6,4}; 
	std::cout<<invertDataPairCount(arr,4); 
}

来自为知笔记(Wiz)