数组中的逆序对 代码(C)

?

?

?

题目: 在数组中的两个数字如果前面一个数字大于后面的数字, 则这两个数字组成一个逆序对.

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

?

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

?

时间复杂度: O(nlogn)

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   
#include 
   
     #include 
    
      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
      
      输出:
      
?
      
result = 5
 
      
?
 
      
?
 
      
 
      
?