归并算法

在做力扣的第51题数组的逆序对时，当时我首先想到的是暴利求解，但是暴利求解在这道题中不能使用，因为力扣会给大量的数据，暴利求解很耗时，因此不能够使用。然后就研究了归并算法的解题思路，首先就是先将数组进行拆分，拆成左右两组数据，然后每组数据在进行拆分，直到剩余一个数据的时候进行，两两排序。下边就套算法吧！

public class Solution {    

        static int count = 0;    

        public int ReversePairs(int[] nums) {        

                    sort(nums,0,nums.Length-1);        

                    return count;    

        }    

        //进行递归    

        public static void sort(int[] nums,int L, int R){        

                   if(L>=R){            

                    return;        

                    }       

                     int mid = L+((R-L)>>1);        

                     sort(nums, L, mid);        

                    sort(nums, mid+1, R);        

                    merge(nums,L,mid,R);    

        }    

        //进行数组合并    

        public static void merge(int[] nums,int L,int Mid, int R){       

                 int[] temp = new int[R-L+1];       

                 int i =0;        

                 int p1 = L;       

                 int p2 = Mid+1;        

                while(p1<=Mid && p2<=R){    

                            //当左边大于右边的时候，说明在后边，让count++

                            if(nums[p1]>=nums[p2]){                

                                        //左边如果等于右边，让count--

                                            for (int j = p1; j < Mid + 1; j++) {                    

                                                    if (nums[j] == nums[p2]){                        

                                                                count--;                        

                                                                continue;                    

                                                    }                   

                                                     break;               

                                             }               

                                             if ((Mid + 1 - p1) >= 0)  {                    

                                                        count = count + Mid + 1 - p1;                

                                                }            

                                        }           

                                         temp[i++] = nums[p1]<nums[p2]?nums[p1++]:nums[p2++];        

                 }       

                 while(p1<=Mid){            

                        temp[i++] = nums[p1++];       

                 }       

                 while(p2<=R){           

                     temp[i++] = nums[p2++];      

                }        

                for(i=0;i<temp.Length;i++){           

                 nums[L+i] = temp[i];        

                }   

        }

}