【本文鏈接】
http://www.cnblogs.com/hellogiser/p/inversion-pairs-by-merge-sort.html
【題目】
編程之美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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
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);
}
[InversionPair]
inversionPair只需要在merge函數中增加3行代碼記錄即可。先將inversion_pairs初始化為0，當L[i]>R[j]時，更新inversion_pairs=inversion_pairs+（n1-i）,最後返回即可。同時在merge_sort中返回left_pair，right_pair和corss_pair之和即可。
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/6/25
*/
int merge_pair(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
//============================
int inversion_pairs = 0;
//============================
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++;
//============================
inversion_pairs += (n1 - i);
//============================
}
}
delete []L;
delete []R;
//============================
return inversion_pairs;
//============================
}
int inversion_pair(int *A, int p, int r)
{
if (p < r)
{
int q = (p + r) / 2;
//======================================
int left_pair = inversion_pair(A, p, q);
int right_pair = inversion_pair(A, q + 1, r);
int cross_pair = merge_pair(A, p, q, r);
return left_pair + right_pair + cross_pair;
//======================================
}
else
return 0;
}
int InversionPair(int *A, int n)
{
return inversion_pair(A, 0, n - 1);
}
【鏈接】
http://www.cnblogs.com/bovine/archive/2011/09/22/2185006.html
http://blog.csdn.net/zhanglei8893/article/details/6230233
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/inversion-pairs-by-merge-sort.html
