C++ 数据结构 (二) 向量 (8) 归并排序

1
2
3
4
5
6
7
8

template <typename T>
void Vector<T>::mergeSort(Rank lo, Rank hi) { // [lo, hi)
  if (hi - lo < 2) return; // 单元素区间自然有序，否则 ...
  int mi = (lo + hi) >> 1; // 以中点为界
  mergeSort(lo, mi);       // 对前半段排序
  mergeSort(mi, hi);       // 对后半段排序
  merge(lo, mi, hi);       // 二路归并
}

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

template <typename T>
void Vector<T>::merge(Rank lo, Rank mi, Rank hi) {
  T *A = _elem + lo; // 合并后的向量 A[0, hi - lo) = _elem[lo, hi)

  int lb = mi - lo; T *B = new T[lb];  // 前子向量 B[0, lb) = _elem[lo, mi)
  for (Rank i = 0; i < lb; B[i] = A[i++]); // 复制前子向量B

  int lc = hi - mi; T *C = _elem + mi; // 后子向量 C[0, lc) = _elem[mi, hi)
  for (Rank i = 0, j = 0, k = 0; (j < lb) || (k < lc); ) {
    if ((j < lb) &amp;&amp; (lc <= k || (B[j] <= C[k]))) A[i++] = B[j++]; // C[k]已无或不小
    if ((k < lc) &amp;&amp; (lb <= j || (C[k] < B[j]))) A[i++] = C[k++]; // B[j]已无或更大
  } // 该循环实现紧凑，但就效率而言，不如拆分处理
  delete [] B; // 释放临时空间 B
}