数组中的逆序对

import java.util.*;

public class AntiOrder {
    public int count(int[] A, int n) {
        int num = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if(A[i] > A[j]) {
                    num++;
                }
            }
        }
        return num;
    }
}

public class Main {

    public int count(int[] A, int n) {
        // write code here
        if(A == null || n < 2 || n > 5000) {
            return 0;
        }
        return sort(A,0,n - 1);
    }

    public static int sort(int[] arr,int left,int right) {
        if(left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        return sort(arr,left,mid) + sort(arr,mid+1,right) + merge(arr,left,mid,right);
    }

    public static int merge(int[] arr,int left,int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = mid+1;
        int res = 0;
        while(p1 <= mid && p2 <= right) {
           res += arr[p1] > arr[p2] ? (mid - p1 + 1) : 0;
           help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while(p2 <= right) {
            help[i++] = arr[p2++];
        }
        for(int j = 0;j < help.length;j++) {
            arr[left++] = help[j];
        }
        return res;
    }
}

import java.util.*;
//其实也就是求一个数左边有少个比它大的，排序后p2之前的数就是p2的所有逆序对 （R-p2+1）
public class AntiOrder {
   public int count(int[] A,int n) {
    if(A == null || n == 0) return 0;
    return mergSort(A,0,A.length-1);
     }
 
   public int mergSort(int[] arr,int L,int R){
         if(L == R) return 0;
         int mid = L+ ((R-L) >> 1);
         return mergSort(arr,L,mid)+mergSort(arr,mid+1,R)+merg(arr,L,mid,R);
        }
 
     public int merg(int[] arr,int L,int mid,int R){
      int[] help = new int[R-L+1];
      int i = 0;
      int count = 0;
      int p1 = L;
      int p2 = mid+1;
      
      while(p1 <= mid && p2 <= R){
       if(arr[p1] > arr[p2]){
           count += (mid-L)+1;    
        help[i++] = arr[p2++];
       }else{
        help[i++] = arr[p1++];
                }
            }
      
      while(p1 <= mid){
       help[i++] = arr[p1++];
            }
      
      while(p2 <= R){
       help[i++] = arr[p2++];
            }
      
      for (int j = 0; j < help.length; j++) {
    arr[L + j] = help[j];
            }
      
      return count;
        }

}

import java.util.*;
import java.util.*;

public class AntiOrder {
    public static int count(int[] A, int n) {
        // write code here
        int num=0;
        for(int i=0;i<A.length;i++) {
            for(int j=0;j<i;j++) {
                if(A[i]<A[j]) {
                    num++;
                }
            }
        }
        return num;
    }
}

//参考剑指offer，利用归并排序的思想。
public class AntiOrder {
    private int counter = 0;
    public int count(int[] A, int n) {
        if(n == 0) return 0;
        int[] aux = new int[n];
        countCore(A, aux, n, 0, n - 1);
        return counter;
    }
    private void countCore(int[] A, int[] aux, int n, int lo, int hi) {
        if(lo == hi) return;
        int mid = (lo + hi) / 2;
        //先排好序
        countCore(A, aux, n, lo, mid);
        countCore(A, aux, n, mid + 1, hi);
        int i = mid, j = hi;
        //进行归并，从高索引处开始
        for(int k = hi; k >= lo; k--) {
            if(i < lo) {
                aux[k] = A[j--];
            }
            else if(j < mid + 1) {
                aux[k] = A[i--];
            }
            else if(A[i] < A[j]) aux[k] = A[j--];
            else if(A[i] > A[j]) {
                aux[k] = A[i--];
                counter += (j - mid);
            }
            else {
                aux[k] = A[j--];
            }
        }
        //第一次使用native方法啊。将归并的结果复制到数组A中
        System.arraycopy(aux, lo, A, lo, hi - lo + 1);
    }
}

import java.util.*;

public class AntiOrder {
    int num=0;
    public int count(int[] A, int n) {
        merge(A,0,n-1);
        return num;
    }
    private void merge(int[] A,int l,int r){
        if(l>=r)
            return;
        int[] tmp=new int[r-l+1];
        int mid=(l+r)/2;
        merge(A,l,mid);
        merge(A,mid+1,r);
        int i=0,j=l,k=mid+1;
        while(j<=mid&&k<=r){
            if(A[j]<=A[k])
                tmp[i++]=A[j++];
            else{
                tmp[i++]=A[k++];
                num+=mid-j+1;
            }     
        }
        while(j<=mid)
            tmp[i++]=A[j++];
        while(k<=r)
            tmp[i++]=A[k++];
        i=0;
        for(int m=l;m<=r;m++){
            A[m]=tmp[i++];
        }
    }
}

/*
public class AntiOrder {
    int[] treeArr;
    private int lowbit(int x){
        return x&(-x);
    }
    private int getSum(int i){
        int res=0;
        for(;i>0;i-=lowbit(i))
            res+=treeArr[i];
        return res;
    }
    private void add(int i,int val,int n){
        for(;i<=n;i+=lowbit(i))
            treeArr[i]+=val;
    }
    public int count(int[] A, int n) {
        treeArr=new int[n+1];
        ArrayList<Integer> uniqueA=new ArrayList<Integer>();
        int[] disA=new int[n];
        int count=0;
        for(int i=0;i<n;i++)
            disA[i]=A[i];
        Arrays.sort(A);
        for(int i=0;i<n;i++){
            if(!uniqueA.contains(A[i]))
                 uniqueA.add(A[i]);
        }
        for(int i=0;i<n;i++)
            disA[i]= uniqueA.indexOf(disA[i])+1;
        for(int i=n-1;i>=0;i--){
            count+=getSum(disA[i]-1);
            add(disA[i],1,n);
        }
        return count;
    }
}
*/

import java.util.*;

public class InversePairs {
    public static int count(int[] array, int length) {
        if (array == null || length <= 0) {
            return 0;
        }
        //创建辅助数组
        int[] copy = new int[length];
        for (int i = 0; i < length; i++){
            copy[i] = array[i];
        }

        int result = InversePairsCore(array, copy, 0, length - 1);
        return result;    
    }

    //归并排序的合并过程
    public static int InversePairsCore(int[] array, int[] copy, int start, int end) {
        if (start == end) {
            copy[start] = array[start];
            return 0;
        }

        int mid = (end - start) / 2;

        //递归调用
        int left = InversePairsCore(copy, array, start, start + mid);
        int right = InversePairsCore(copy, array, start + mid + 1, end);

        //归并
        int i = start + mid;  // i 初始化为前半段最后一个数字的下标
        int j = end;  // j 初始化为后半段最后一个数字的下标
        int indexCopy = end;
        int count = 0;  //记录相邻子数组间的逆序数

        //每次比较两个末尾值
        while (i >= start && j >= start + mid + 1) {
            //如果前末尾值大于后末尾值，则有“后序列当前长度”个逆序对
            if (array[i] > array[j]) {
                copy[indexCopy--] = array[i--];
                count += j - mid - start;
            }
            //否则不构成逆序对
            else {
                copy[indexCopy--] = array[j--];
            }
        }

        while(i >= start) {
            copy[indexCopy--] = array[i--];
        }
        while(j >= start + mid + 1) {
            copy[indexCopy--] = array[j--];
        }

        return left + right + count;
    }
}