C++ 数据结构 (一) 绪论 (5) 迭代与递归 (3)

1
2
3
4
5
6
7
8
9
10
11
12

void max2(int A[], int lo, int hi, int &x1, int &x2) // 1 < n = hi - lo
{
  for (x1 = lo, int i = lo + 1; i < hi; i++) {       // 扫描 A[lo, hi), 找出 A[x1]
    if (A[x1] < A[i]) x1 = i;                        // hi - lo - 1 = n - 1
  }
  for (x2 = lo, int i = lo + 1; i < x1; i++) {       // 扫描 A[lo, x1)
    if (A[x2] < A[i]) x2 = i;                        // xi - lo - 1
  }
  for (int i = x1 + 1; i < hi; i++) {                // 再扫描 A(x1, hi), 找出 A[x2]
    if (A[x2] < A[i]) x2 = i;                        // hi - x1 - 1
  }
}

1
2
3
4
5
6
7
8
9

void max2(int A[], int lo, int hi, int &x1, int &x2) // 1 < n = hi - lo
{
  if (A[x1 = lo] < A[x2 = lo + 1]) swap(x1, x2);     // 1
  for (int i = lo + 2; i < hi; i++) {                // hi - lo - 2 = n - 2
    if (A[x2] < A[i]) {
      if (A[x1] < A[x2 = i]) swap(x1, x2);
    }
  }
}

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

void max2(int A[], int lo, int hi, int &x1, int &x2) {
  if (lo + 2 == hi) {
    if (A[x1 = lo] < A[x2 = lo + 1]) swap(x1, x2); return;
  } // T(2) = 1

  if (lo + 3 == hi) {
    if (A[x1 = lo] < A[x2 = lo + 1]) swap(x1, x2);
    if (A[x2] < A[lo + 2]) x2 = lo + 2;
    if (A[x1] < A[x2]) swap(x1, x2);
    return;
  } // T(3) <= 3

  int mi = (lo + hi) / 2;

  int x1L, x2L; max2(A, lo, mi, x1L, x2L); // T(n/2)

  int x1R, x2R; max2(A, mi, hi, x1R, x2R); // T(n/2)

  if (A[x1L] > A[x1R]) {
    x1 = x1L;
    x2 = (A[x2L] > A[x1R]) ? x2L : x1R;
  } else {
    x1 = x1R;
    x2 = (A[x2R] > A[x1L]) ? x2R : x1L;
  } // 1 + 1 = 2

} // T(n) = 2 * T(n/2) + 2 <= 5n/3 - 2