剑指offer——数组中的逆序对

题目链接：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007

解题思路：

归并排序

 1 public class Solution {
 2     int count;
 3     public int InversePairs(int [] array) {
 4         if(array.length==0 || array==null)
 5             return 0;
 6         SortProcess(array,0,array.length-1);
 7         return count;
 8     }
 9     public void SortProcess(int []arr,int start,int end)
10     {
11         if(start==end)
12             return ;
13         int mid = start+(end-start)/2;
14     
15         SortProcess(arr,start,mid);
16         SortProcess(arr,mid+1,end);
17 
18         Merge(arr,start,mid,end);
19         
20     }
21     public void Merge(int []arr,int start,int mid,int end)
22     {
23         int [] help = new int[end-start+1];
24         int i=0;
25         int p1 = start;
26         int p2 = mid+1;
27         while(p1<=mid&&p2<=end)
28         {
29             if(arr[p1]<arr[p2])
30             {
31                 help[i] = arr[p1];
32                 p1++;
33             }
34             else
35             {
36                 help[i] = arr[p2];
37                 count = (count+mid-p1+1)%1000000007;
38                 p2++;
39             }
40             i++;
41         }
42         while(p1<=mid){
43             help[i++] = arr[p1++];
44         }
45         while(p2<=end){
46             help[i++]=arr[p2++];
47         }
48         
49         for(i=0;i<help.length;i++){
50             arr[start+i] = help[i];
51         }
52     }
53     
54 }