剑指 Offer 51. 数组中的逆序对

归并排序求逆序对
归并要熟悉

class Solution {
    //归并排序的应用
    int[] nums,number;
    int cnt=0;
    public int reversePairs(int[] nums) {
        this.nums=nums;//这种声明和定义方式借助题解，可以少传递参数
        number=new int[nums.length];   
       return mergeSort(0,nums.length-1);
    }
    int mergeSort(int left,int right){//[left,right]
      if(left>=right)//如果写成right==left?
         return 0;

      //int mid=(left+right)/2;
      int mid=left+(right-left)/2;//注意当left和right很大时用这个计算中点

      cnt=mergeSort(left,mid)+mergeSort(mid+1,right);
      //关于递归，回溯。记住函数的功能或返回值，当成已经实现了，不必深究，然后好在递归调用下写代码 
      //划分结束(这个把划分和归并写到一起了)，接下来是归并
      //[left,mid]和[mid+1,right]是两个有序数组
      //把分治和归并写在一起是参考题解
      for(int i=left;i<=right;i++){//将待排序部分的数组拷贝到辅助数组中
          number[i]=nums[i];
      }
      //循环条件和下标更新方式是邓老师的风格
      for(int i=left,p=left,q=mid+1;(p<=mid||q<=right);){//p,q分别指向两个有序数组的第一个元素
                                                         //从左边开始将排序好的元素一一填入原始数组
          if((p<=mid)&&(q>right||number[p]<=number[q]))//这个小于等于好是保证稳定性的关键
            nums[i++]=number[p++];//这个判断要注意，如果右边数组已经没有元素了，也要把左边数组依次填入
          if((q<=right)&&(p>mid||number[p]>number[q])){
            nums[i++]=number[q++];
            cnt=cnt+mid-p+1;
             }
      }

      return cnt;
      

    }
}

剑指 Offer 51. 数组中的逆序对

原文：https://www.cnblogs.com/wsshub/p/14729888.html