【题目】

　　编程之美1.7光影切割问题可以进一步将问题转化为求逆序数问题。

　　【分析】

　　求解逆序对问题与MergeSort类似，只需要对MergeSort稍作修改即可实现。MergeSort是采用分治法的思想，若需要排序A[p...r]，则可以对半分成A[p...q]和A[q...r]，然后将这有序的两部分Merge，而Merge的过程为Θ(n)的时间复杂度。根据主定率T(n)=2(Tn/2)+Θ(n)，时间复杂度为T(n)=Θ(nlgn)。

　　同理，求整个序列中的逆序对，也可以利用分治法的思想，即

　　逆序对(A[p...r]）= 逆序对(A[p...q])+逆序对(A[q...r])+逆序对(A[p...q], A[q...r]之间） 。

　　结合MergeSort，关键是如何在Θ(n)的时间有效的求出A[p...q], A[q...r]之间的逆序对。因为在合并排序的Merge过程中，A[p...q]和A[q...r]已经有序，假设此时已经Merge到A[i...q]和A[j...r]。考虑接下来的一步：如果A[i]<=A[j],说明A[i]比后面的序列A[j...r]中的元素都小，不存在逆序对;如果A[i]>A[j],，则说明A[j]比前面的序列A[i...q]都小，即以j结尾的逆序对的数量为前面的序列剩余序列A[i...q]中元素的数量。

　　Merge的过程中即可得到A[p...r], A[r...q]之间的逆序对的数量，时间复杂度亦为Θ(n), 由主定律总的时间复杂为 Θ(nlgn) ，这种方法要比朴素的方法 Θ(n*n)好很多。

　　【MergeSort】

　　C++ Code 

         /*

　　version: 1.0

　　author: hellogiser

　　blog: http://www.cnblogs.com/hellogiser

　　date: 2014/6/25

　　*/

　　void merge(int *A, int p, int q, int r)

　　{

　　//Li: p...q Rj: q+1...r

　　int n1 = q - p + 1;

　　int n2 = r - (q + 1) + 1;

　　int *L = new int[n1 + 1];

　　int *R = new int[n2 + 1];

　　// copy L and R

　　for (int i = 0; i < n1; i++)

　　L[i] = A[p + i];

　　for (int j = 0; j < n2; j++)

　　R[i] = A[q + 1 + j];

　　// mark end

　　L[n1] = INT_MAX;

　　R[n2] = INT_MAX;

　　int i = 0; // left

　　int j = 0; // right

　　int k = 0; // whole

　　for (k = p; k <= r; k++)

　　{

　　if (L[i] <= R[j])

　　{

　　A[k] = L[i];

　　i++;

　　}

　　else

　　{

　　// L[i]>R[j]

　　A[k] = R[j];

　　j++;

　　}

　　}

　　delete []L;

　　delete []R;

　　}

　　void merge_sort(int *A, int p, int r)

　　{

　　if (p < r)

　　{

　　int q = (p + r) / 2;

　　merge_sort(A, p, q);

　　merge_sort(A, q + 1, r);

　　merge(A, p, q, r);

　　}

　　}

　　void MergeSort(int *A, int n)

　　{

　　merge_sort(A, 0, n - 1);

　　}