深入探讨两道与归并排序相关的算法题目

1 #include
2 #include
3
4 using namespace std;
5
6 int x = 5;
7
8 bool merge(int a[], int p, int q, int r)
9 {
10 int i = p; int j = r - 1;
11 while (i = q)
12 {
13 int asum = a[i] + a[j];
14 if (asum == x)
15 return true;
16 else if (asum > x)
17 j--;
18 else
19 i++;
20 }
21
22 int* L = new int[q - p + 1];
23 int* R = new int[r - q + 1];
24
25 for (int i = 0; i )
26 L[i] = a[p + i];
27 for (int i = 0; i )
28 R[i] = a[q + i];
29
30 L[q - p] = numeric_limits<int>::max();
31 R[r - q] = numeric_limits<int>::max();
32
33 i = 0; j = 0;
34
35 for (int k = p; k )
36 {
37 if (L[i] < R[j])
38 {
39 a[k] = L[i];
40 i++;
41 }
42 else
43 {
44 a[k] = R[j];
45 j++;
46 }
47 }
48
49 delete[] L;
50 delete[] R;
51 return false;
52 }
53
54 bool merge_find(int a[], int p, int r)
55 {
56 if (r - p <= 1)
57 return false;
58 int q = (p + r) / 2;
59 if (merge_find(a, p, q))
60 return true;
61 if (merge_find(a, q, r))
62 return true;
63 if (merge(a, p, q, r))
64 return true;
65 return false;
66 }
67
68 int main(int argc, char** argv)
69 {
70 int a[] = { 1, 1, 3, 5, 3, 5};
71
72 bool flag = merge_find(a, 0, 6);
73
74 cout < endl;
75
76 return 0;
77 }

1 #include
2 #include
3
4 using namespace std;
5
6 int merge(int a[], int p, int q, int r)
7 {
8 int invnum = 0;
9 int j = q;
10 for (int i = p; i )
11 {
12 while (j a[i])
13 {
14 j++;
15 }
16 invnum += j - q;
17 }
18
19 int* L = new int[q - p + 1];
20 int* R = new int[r - q + 1];
21
22 for (int i = 0; i )
23 L[i] = a[p + i];
24 for (int i = 0; i )
25 R[i] = a[q + i];
26
27 L[q - p] = numeric_limits<int>::max();
28 R[r - q] = numeric_limits<int>::max();
29
30 int i = 0;
31 j = 0;
32
33 for (int k = p; k )
34 {
35 if (L[i] < R[j])
36 {
37 a[k] = L[i];
38 i++;
39 }
40 else
41 {
42 a[k] = R[j];
43 j++;
44 }
45 }
46
47 delete[] L;
48 delete[] R;
49 return invnum;
50 }
51
52 int merge_find_inverse(int a[], int p, int r)
53 {
54 if (r - p <= 1)
55 return 0;
56 int q = (p + r) / 2;
57 int n1 = merge_find_inverse(a, p, q);
58 int n2 = merge_find_inverse(a, q, r);
59 int n3 = merge(a, p, q, r);
60 return n1 + n2 + n3;
61 }
62
63 int main(int argc, char** argv)
64 {
65 int a[] = { 3, 2, 1};
66
67 int flag = merge_find_inverse(a, 0, 3);
68
69 cout < endl;
70
71 return 0;
72 }