常用算法（后面有inplace版本）：

1 package ArrayMergeSort; 2  3 import java.util.Arrays; 4  5 public class Solution { 6     public int[] mergeSort(int[] arr) { 7         if (arr.length == 1) return arr; 8         else { 9             int[] arr1 = Arrays.copyOfRange(arr, 0, arr.length/2);10             int[] arr2 = Arrays.copyOfRange(arr, arr.length/2, arr.length);11             return merge(mergeSort(arr1), mergeSort(arr2));12         }13     }14     15     public int[] merge(int[] arr1, int[] arr2) {16         int len1 = arr1.length;17         int len2 = arr2.length;18         int[] res = new int[len1+len2];19         int i = 0, j=0, cur=0;20         while (i

 在如上算法中只需稍作修改，加上一行代码，就可以求数组的逆序对

如数组 <2,3,8,6,1> 的逆序对为：<2,1> <3,1> <8,6> <8,1> <6,1> 共5个逆序对。

暴力法是O（N^2）

mergeSort可以O（NlogN）

定义一个static variable count, 然后在12行加入

1 public int[] merge(int[] arr1, int[] arr2) { 2         int len1 = arr1.length; 3         int len2 = arr2.length; 4         int[] res = new int[len1+len2]; 5         int i = 0, j=0, cur=0; 6         while (i
     
       arr2[j];11                 res[cur++] = arr2[j++];12                 count += arr1.length - i;13             }14         }15         while (i
     

 

Inplace的mergeSort不是那么好写，我还是在merge的时候用了额外空间

1 package ArrayMergeSort; 2  3 import java.util.Arrays; 4  5 public class Solution2 { 6      7     public int[] mergeSort(int[] arr) { 8         if (arr==null || arr.length==0) return arr; 9         mergeSort(arr, 0, arr.length-1);10         return arr;11     }12     13     public void mergeSort(int[] arr, int l, int r) {14         if (r-l == 0) return;15         int m = (l+r)/2;16         mergeSort(arr, l, m);17         mergeSort(arr, m+1, r);18         merge(arr, l, m, m+1, r);19     }20     21     public void merge(int[] arr, int l1, int r1, int l2, int r2) {22         int[] temp = new int[r2-l1+1];23         int i1=l1, i2=l2, cur=0;24         while (i1<=r1 && i2<=r2) {25             if (arr[i1] <= arr[i2]) temp[cur]=arr[i1++];26             else temp[cur] = arr[i2++];27             cur++;28         }29         while(i1<=r1) temp[cur++]=arr[i1++];30         while(i2<=r2) temp[cur++]=arr[i2++];31         cur = 0;32         for (int i=l1; i<=r2; i++) arr[i]=temp[cur++];33     }34 35     /**36      * @param args37      */38     public static void main(String[] args) {39         // TODO Auto-generated method stub40         Solution2 sol = new Solution2();41         int[] arr = sol.mergeSort(new int[]{6,5,4,2,1});42         System.out.println(Arrays.toString(arr));43     }44 45 }

 Iterative Merge Sort大致的算法是，假设每一层需要merge许多数组 A和B数组是其中两个，i 可以理解为A或B的size，从1一直到array.length/2. j 可以理解为一组A和B之中B的结束位置。 Merge函数跟上面一样

1 Iterative Merge Sort 2 public static T[] Iterative(T[] array, IComparer
     
       comparer) 3 { 4     for (int i = 1; i <= array.Length / 2 + 1; i *= 2) 5     { 6         for (int j = i; j < array.Length; j += 2 * i) 7         { 8             Merge(array, j - i, j, Math.Min(j + i, array.Length), comparer); 9         }10     }11  12     return array;13 }