2.1.0 归并排序

归并排序，时间复杂度O(N * log N) 额外空间复杂度O(N)

public class MergeSort {
    
    public static void sort(int[] array) {
        if(array == null || array.length <2) return;
        mergesort(array, 0, array.length-1);
        return;
        
    }
    
    public static void mergesort(int[] array, int leftIndex, int rightIndex) {
        if(leftIndex >= rightIndex) return;
        int mid = leftIndex + ((rightIndex - leftIndex) >>1);
        mergesort(array, leftIndex, mid);
        mergesort(array, mid+1,rightIndex);
        merge(array,leftIndex,rightIndex,mid);
        return;
    }
    
    public static void merge(int[] array, int leftIndex, int rightIndex, int mid) {
        int[] tempArray = new int[rightIndex - leftIndex + 1];
        int left = leftIndex;
        int right = mid + 1;
        int pos = 0;
        
        while(left <= mid && right <= rightIndex) {
            if(array[left] <= array[right]) {
                tempArray[pos++] = array[left++];
            }else {
                tempArray[pos++] = array[right++];
            }
        }
        
        while(left <= mid) {
            tempArray[pos++] = array[left++];
        }
        
        while(right <= mid) {
            tempArray[pos++] = array[right++];
        }
        System.arraycopy(tempArray, 0, array, leftIndex, tempArray.length);
        return;
    }
    
    public static void main(String[] args)throws Exception {
        int [] arr = {4,3,2,1};
        MergeSort sol = new MergeSort();
        sol.sort(arr);
        for(int i=0; i < arr.length;i++) {
            System.out.println(arr[i]);
        }
    }

}

小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和
如[1, 3, 4, 2, 5]的
小和为(0)+(1)+(1+3)+(1)+(1+3+4+2)
直接解法，暴力遍历O(N^2)

public class SmallSum {

    public static int sum = 0;

    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2)
            return 0;
        return subSmallSum(arr, 0, arr.length - 1);
    }

    public static int subSmallSum(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex)
            return 0;
        int mid = leftIndex + ((rightIndex - leftIndex) >> 1);
        return subSmallSum(arr, leftIndex, mid) + subSmallSum(arr, mid + 1, rightIndex)
                + mergeCount(arr, leftIndex, rightIndex, mid);
    }

    public static int mergeCount(int[] arr, int leftIndex, int rightIndex, int mid) {
        int[] temparr = new int[rightIndex - leftIndex + 1];
        int left = leftIndex;
        int right = mid + 1;
        int pos = 0;
        int sum = 0;
        while (left <= mid && right <= rightIndex) {
            if (arr[left] < arr[right]) {
                sum += arr[left] * (rightIndex - right + 1);
                temparr[pos++] = arr[left++];
            } else {
                temparr[pos++] = arr[right++];
            }

        }

        while (left <= mid) {
            temparr[pos++] = arr[left++];
        }

        while (right <= rightIndex) {
            temparr[pos++] = arr[right++];
        }
                System.arraycopy(temparr, 0, arr, leftIndex, temparr.length);
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 3, 4, 2, 5 };

        System.out.println(smallSum(arr));
    }

}

逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，求所有逆序对

public class ReverseCouple {
    public static List<int[]> countReverseCouple(int [] arr){
        if(arr == null || arr.length < 2) return new ArrayList<int[]>();
        return countReverseCoupleSub(arr, 0, arr.length -1);
    }
    
    public static List<int[]> countReverseCoupleSub(int[] arr, int left, int right) {
        if(left >=right) {
            return new ArrayList<int[]>();
        }
        List<int[]> res = new ArrayList<>();
        int mid = left + ((right - left)>>1);
        res.addAll(countReverseCoupleSub(arr, left, mid));
        res.addAll(countReverseCoupleSub(arr, mid + 1, right));
        res.addAll(merge(arr, left, mid, right));
        return res; 
    }
    
    public static List<int[]> merge(int[] arr, int leftIndex, int mid, int rightIndex){
        List<int[]> res = new ArrayList<>();
        if(rightIndex <= leftIndex) return res;
        int[] tempArr = new int[rightIndex - leftIndex + 1];
        int left = mid;
        int right = rightIndex;
        int pos = tempArr.length -1;

        while(left >= leftIndex  && right >= mid + 1) {
            
            if(arr[left] > arr[right]) {
                for(int i = mid+1; i<=right; i++) {
                    int[] temp = new int[2];
                    temp[0] = arr[left];
                    temp[1] = arr[i];
                    res.add(temp);
                }
                tempArr[pos--] = arr[left--];
            }else {
                tempArr[pos--] = arr[right--];
            }
        }
        
        while(left >= leftIndex) {
            tempArr[pos--] = arr[left--];
        }
        while(right >= mid + 1) {
            tempArr[pos--] = arr[right--];
        }
        System.arraycopy(tempArr, 0, arr, leftIndex, tempArr.length);
        return res;
    }
    
    public static void main(String[] args) {
        int[] arr = { 1, 3, 4, 2, 5 };
        System.out.println(countReverseCouple(arr).size());
    }

}