面试题36 数组中的逆序对

归并排序的变形应用

int inversePairs(int data[], int len)
{
	if(data == NULL || len <1) return 0;
	
	int *copy = new int[len];
	
	for(int i = 0; i< len ; ++i)
		copy[i] = data[i];
		
	int res = InverseP(data, copy, 0, len-1);
	
	delete [] copy;
	
	return count;
}

int InverseP(int *data, int *copy, int start, int end)
{
	if(start == end){
		copy[start] = data[start];
		return 0;
	}
	
	int half =  (end - start)>>1;
	
	int left = InverseP(copy, data, start, start + half -1);
	int right = InverseP(copy, data, start + half, end);
	
	int i = start + half -1;
	int j = end;
	int index = end;
	int count = 1;
	while(i>= start && j >= start + half){
		if(data[i] > data[j]){
			copy[index--] = data[i--];
			count += j - start - half +1;
		}else{
			copy[index--] = data[j--];
		}
	}
	while(i>=start) copy[index--] = data[i--];
	while(j>= start + half) copy[index--] = data[j--];
	
	return left + right + count; 
}