归并排序

归并排序是采用分治的一种排序方法：
先将元素分开，也就长度为1的有序序列。
合并有序序列，直至合并成一个数组
百度的代码：

package algorithm;
 
public class MergeSort {
    //　private　static　long　sum　=　0;
 
    /**
     * 　*　<pre>
     * 　*　二路归并
     * 　*　原理：将两个有序表合并和一个有序表
     * 　*　</pre>
     * 　*
     * 　*　@param　a
     * 　*　@param　s
     * 　*　第一个有序表的起始下标
     * 　*　@param　m
     * 　*　第二个有序表的起始下标
     * 　*　@param　t
     * 　*　第二个有序表的结束下标
     * 　*
     */
    private static void merge(int[] a, int s, int m, int t) {
        int[] tmp = new int[t - s + 1];
        int i = s, j = m, k = 0;
        while (i < m && j <= t) {
            if (a[i] <= a[j]) {
                tmp[k] = a[i];
                k++;
                i++;
            } else {
                tmp[k] = a[j];
                j++;
                k++;
            }
        }
        while (i < m) {
            tmp[k] = a[i];
            i++;
            k++;
        }
        while (j <= t) {
            tmp[k] = a[j];
            j++;
            k++;
        }
        System.arraycopy(tmp, 0, a, s, tmp.length);
    }
 
    /**
     * 　*
     * 　*　@param　a
     * 　*　@param　s
     * 　*　@param　len
     * 　*　每次归并的有序集合的长度
     */
    public static void mergeSort(int[] a, int s, int len) {
        int size = a.length;
        int mid = size / (len << 1);
        int c = size & ((len << 1) - 1);
        //　-------归并到只剩一个有序集合的时候结束算法-------//
        if (mid == 0)
            return;
        //　------进行一趟归并排序-------//
        for (int i = 0; i < mid; ++i) {
            s = i * 2 * len;
            merge(a, s, s + len, (len << 1) + s - 1);
        }
        //　-------将剩下的数和倒数一个有序集合归并-------//
        if (c != 0)
            merge(a, size - c - 2 * len, size - c, size - 1);
        //　-------递归执行下一趟归并排序------//
        mergeSort(a, 0, 2 * len);
    }
 
    public static void main(String[] args) {
        int[] a = new int[]{4, 3, 6, 1, 2, 5};
        mergeSort(a, 0, 1);
        for (int i = 0; i < a.length; ++i) {
            System.out.print(a[i] + "　");
        }
    }
}

数组逆序序列AC，抄的代码:

public class Solution {
   public int InversePairs(int [] array) {
        if(array.length == 0||array  == null){
            return 0;

        }
        int[] copy = new int[array.length];
        System.arraycopy(array,0,copy,0,array.length);
        return Merge(array,copy,0,array.length-1);
    }
    public int Merge(int array[],int copy[],int start,int end){
        if(start == end){
            return 0;
        }
        int mid = (start + end)>>1;
        int left = Merge(array,copy,start,mid)% 1000000007;
        int right = Merge(array,copy,mid+1,end)%1000000007;
        int  count = 0;
        int i = mid;
        int j = end;
        int tmp = end;
        while(i>=start && j>mid){
            if(array[i]>array[j]){
                count += j - mid;
                copy[tmp--] = array[i--];
                if(count > 1000000007){
                    count = count - 1000000007;
                }
            }
            else{
                copy[tmp--] = array[j--];
            }
        }
        while (i>=start){
            copy[tmp--] = array[i--];
        }
        while (j>mid){
            copy[tmp--] = array[j--];
        }
            System.arraycopy(copy,start,array,start,end-start+1);
        return (count + left + right)%1000000007;
    }
}