歸并排序與逆序對

在刷題的過程中碰到了關于無序序列的逆序對統計的問題。

直接暴力會超時，然后搜索了一下算法，發現可以通過歸并排序的思想來做到這個統計的過程。看代碼的時候，不知道自己的理解力不夠還是不熟悉別人的代碼，反正是看不懂。無奈之下自己按照自己的理解實現了一下這個算法，順便復習了一下歸并排序算法，所以有了這么一篇文章。算是個筆記吧。

思想很簡單:

1. 數組分成左右兩部分
2. 兩個子數組排序
3. 兩個數組合并，這個合并的過程中，如果左邊的key值大于右邊的key值，就產生了逆序對。因為左邊數組是有序的，所以，這個時候產生的逆序對的個數是剩余未處理的部分的長度，將這個數值統計起來就是我們要的結果。
4. 算法復雜度為$nlog_2 n$。

class MergeSort
{public int sort(int[] array, int p, int r){if (p < r){int q = p + (r - p) / 2;int len1 = sort(array, p, q);      //子數組排序int len2 = sort(array, q + 1, r);int count = merge(array, p, q, r);return len1 + len2 + count;}else{return 0;}}public int merge(int[] array, int p, int q, int r){int n1 = q - p + 1;int n2 = r - q;int[] array1 = new int[n1 + 1];int[] array2 = new int[n2 + 1];array1[n1] = int.MaxValue;array2[n2] = int.MaxValue;for (int i = 0; i < n1; i++){array1[i] = array[p + i];}for (int i = 0; i < n2; i++){array2[i] = array[q + 1 + i];}int index1 = 0, index2 = 0;int count = 0;for (int i = p; i <= r; i++){if (array1[index1] <= array2[index2]){array[i] = array1[index1++];}else{array[i] = array2[index2++];count += n1 - index1;//數組有序，所以剩下幾個key就有一個key比array2[index2]大也就是有幾個逆序對。}}return count;}
}

算法的有效性：

1. 因為合并前，左右數組有序
2. 左邊的key值如果大于右邊的key值，就代表有逆序對產生。因為數組有序，這樣左邊剩余的key值肯定更大，所以剩余幾個key就有幾個逆序對。
3. 算法的整個過程是遞歸實現的，比較小的key值是一點一點移動到前面來消除逆序對，這個過程是沒有逆向的。