演算法精講：歸併排序原理與 C++ 實現

歸併排序核心思想：將兩個有序表合併為一個有序表。時間複雜度穩定為 O(n log₂n)（最好/最壞同），空間複雜度 O(N)，屬穩定排序。缺點是合併需 O(N) 額外空間。

分治策略

1. 分解：將 n 元素序列分成兩個 n/2 子序列。
2. 解決：遞歸歸併排序兩子序列。
3. 合併：將兩有序子序列合併為有序答案。

合併操作詳解

輔助函數 merge(A, p, q, r, T)：假設 A[p..q] 和 A[q+1..r] 已排序，合併為單一有序子陣列替換 A[p..r]。時間 O(n)。

void mergearray(int a[], int first, int mid, int last, int temp[]) {
  int i = first, j = mid + 1, k = 0;
  while (i <= mid && j <= last) {
    if (a[i] <= a[j]) temp[k++] = a[i++];
    else temp[k++] = a[j++];
  }
  while (i <= mid) temp[k++] = a[i++];
  while (j <= last) temp[k++] = a[j++];
  for (i = 0; i < k; i++) a[first + i] = temp[i];
}

遞歸排序主函數

void mergesort(int a[], int first, int last, int temp[]) {
  if (first < last) {
    int mid = (first + last) / 2;
    mergesort(a, first, mid, temp);
    mergesort(a, mid + 1, last, temp);
    mergearray(a, first, mid, last, temp);
  }
}

int MergeSort(int a[], int n) {
  int *p = new int[n];
  if (!p) return FALSE;
  mergesort(a, 0, n - 1, p);
  delete[] p;
  return TRUE;
}

測試程式

int main() {
  int array[] = {6, 2, 3, 1, 4, 5};
  MergeSort(array, 6);
  for (int i = 0; i < 6; i++) printf("%d\t", array[i]);
  return 0;
}

下一篇將講解堆排序。本文出自「驛落黃昏」博客，轉載請保留出處：https://yiluohuanghun.blog.51cto.com/3407300/1271618