剑指Offer34 数组中的逆序对

 /*************************************************************************

     > File Name: 34_InversePairsInArray.c

     > Author: Juntaran

     > Mail: [email protected]

     > Created Time: 2016年09月02日 星期五 20时05分05秒

  ************************************************************************/

 #include <stdio.h>

 #include <malloc.h>

 int InversePairsCore(int* nums, int* copy, int left, int right)

 {

     if (left == right)

     {

         copy[left] = copy[right];

         return ;

     }

     int newlength = (right - left) / ;

     // 递归

     int leftCount  = InversePairsCore(copy, nums, left, left+newlength);

     int rightCount = InversePairsCore(copy, nums, left+newlength+, right);

     // i初始化为前半段最后一个数字下标

     int i = left + newlength;

     // j初始化为后半段最后一个数字下标

     int j = right;

     int indexCopy = right;

     int count = ;

     while (i>=left && j>=left+newlength+)

     {

         if (nums[i] > nums[j])

         {

             copy[indexCopy--] = nums[i--];

             count += j - left - newlength;

         }

         else

         {

             copy[indexCopy--] = nums[j--];

         }

     }

     for (i; i >= left; --i)

         copy[indexCopy--] = nums[i];

     for (j; j>=left+newlength+; --j)

         copy[indexCopy--] = nums[j];

     return leftCount + rightCount + count;

 }

 int InversePairs(int* nums, int length)

 {

     if (nums==NULL || length<=)

         return -;

     int* copy = (int*)malloc(sizeof(int)*length);

     for (int i = ; i < length; ++i)

         copy[i] = nums[i];

     int count = InversePairsCore(nums, copy, , length-);

     delete[] copy;

     return count;

 }

 int main()

 {

     int nums[] = {,,,};

     int length = ;

     int ret = InversePairs(nums, length);

     printf("%d\n", ret);

 }