如何实现数组中的逆序对

如何实现数组中的逆序对2015-10-12题目: 在数组中的两个数字如果前面一个数字大于后面的数字, 则这两个数字组成一个逆序对.

输入一个数组, 求出这个数组中的逆序对的总数.

使用归并排序的方法, 辅助空间一个排序的数组, 依次比较前面较大的数字, 算出整体的逆序对数, 不用逐个比较.

时间复杂度: O（nlogn）

代码:

/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>#include <stdlib.h>#include <string.h>int InversePairsCore（int* data, int* copy, int start, int end） {if （start == end） {copy[start] = data[start];return 0;}int length = （end-start）/2;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 indexCopy = end;int count = 0;while （i>=start && j>=start+length+1） {if （data[i] > data[j]） {copy[indexCopy--] = data[i--];count += j-start-length;} else {copy[indexCopy--] = data[j--];}}for （; i>=start; --i）copy[indexCopy--] = data[i];for （; j>=start+length+1; --j）copy[indexCopy--] = 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（void）{int data[] = {7, 5, 6, 4};int result =InversePairs （data, 4）;printf（"result = %d
", result）;return 0;}

输出:

result = 5

作者：csdn博客 Caroline-Wendy