Coursera Algorithms week3 歸併排序 練習測驗: Counting inversions

題目原文：

An inversion in an array a[] is a pair of entries a[i] and a[j] such that i<j but a[i]>a[j]. Given an array, design a linearithmic algorithm to count the number of inversions.

分析：

如果沒有性能限制，用插入排序演算法可以實現。題目性能被限制在nlogn，又是歸併排序的練習題，很顯然要實現個歸併排序，併在裡面計數。通過一個例子來看下計數方法，例如{6, 5, 2, 3, 4, 1}這個序列，歸併過程中會分為分為如下幾步：

1. 歸併{6, 5}，存在一次右側元素5移至左側的操作，變成{5, 6}，歸併前逆序對<6,5>

2. 歸併{5, 6, 2}，存在一次右側元素2移至左側的操作, 變成{2, 5, 6}，歸併前存在兩對逆序對<5, 2>和<6, 2>

3. 歸併{3, 4}，不存在右側元素左移操作

4. 歸併{3, 4, 1}，存在一次右側元素1移至左側的操作，變成{1, 3, 4}，歸併前存在兩對逆序對<3, 1>和<4, 1>

5. 歸併{2, 5, 6, 1, 3, 4}，存在三次1、3、4右側元素移至左側的操作，歸併前存在七對逆序對<2,1><5,1><6,1><5,3><6,3><5,4><6,4>

由上述分析可見，當右側元素a[j]與左側元素a[i]進行比較後需要移至左側時，a[j]與區間 [ a[i] , a[mid] ]中的所有元素都可以組成逆序對，這個區間的元素個數為mid+1-i個。

因此代碼如下：

 1 import java.util.Arrays;
 2 
 3 /**
 4  * @author evasean www.cnblogs.com/evasean/
 5  */
 6 public class CountInversions {
 7     private static Comparable[] aux;
 8     private static int num = 0; // 逆序對計數
 9 
10     private static boolean less(Comparable v, Comparable w) {
11         return v.compareTo(w) < 0;
12     }
13 
14     public static int inversionsNum(Comparable[] a) {
15         aux = new Comparable[a.length];
16         sort(a, 0, a.length - 1);
17         return num;
18     }
19 
20     private static void sort(Comparable[] a, int lo, int hi) {
21         if (hi <= lo)
22             return;
23         int mid = lo + (hi - lo) / 2;
24         sort(a, lo, mid);
25         sort(a, mid + 1, hi);
26         merge(a, lo, mid, hi);
27     }
28 
29     private static void merge(Comparable[] a, int lo, int mid, int hi) {
30         int i = lo;
31         int j = mid + 1;
32         for (int k = lo; k <= hi; k++) {
33             aux[k] = a[k];
34         }
35         for (int k = lo; k <= hi; k++) {
36             if (i > mid)  // i>mid表示aux的左半側已經被全部被放於a中，直接將右半側部分放入a
37                 a[k] = aux[j++];
38             else if (j > hi) // j>hi表示aux的右半側已經被全部被放於a中，直接將左半側部分放入a
39                 a[k] = aux[i++]; 
40             else if (less(aux[j], aux[i])){ // 右側元素小於左側元素時，將右側元素放入
41                 num += mid+1-i; //此時右側的這個元素a[j]和[a[i],a[mid]]整個區間的元素都是逆序對
42                 a[k] = aux[j++];
43             }else a[k] = aux[i++];
44         }
45         //System.out.println(Arrays.toString(a));
46     }
47 
48     public static void main(String[] args) {
49         Integer[] a = { 6,5,2,3,4,1 };
50         System.out.println(inversionsNum(a));
51         System.out.println(Arrays.toString(a));
52     }
53 }