歸並排序 的核心操作是合併：將兩個已排序的序列合併為一個更大的有序序列。本文聚焦於「合併」本身——給定兩個升序數組，如何高效合併為一個升序數組。這既是歸並排序的關鍵子過程，也是獨立實用的算法模塊。
i 遍歷數組 A，j 遍歷數組 B，k 寫入結果數組 C。A[i] 與 B[j]，將較小者放入 C[k]，對應索引前移。#include#include #define M 6 #define N 4 int main() { int a[M] = {-3, 6, 19, 26, 68, 100}; int b[N] = {8, 10, 12, 22}; int c[M+N]; int i = 0, j = 0, k = 0, l; printf("a 數組元素:\n"); for (l = 0; l < M; l++) printf("%d ", a[l]); printf("\n"); printf("b 數組元素:\n"); for (l = 0; l < N; l++) printf("%d ", b[l]); printf("\n"); // 核心合併邏輯 while (i < M && j < N) { if (a[i] <= b[j]) { c[k++] = a[i++]; } else { c[k++] = b[j++]; } } // 拷貝剩餘元素 while (i < M) c[k++] = a[i++]; while (j < N) c[k++] = b[j++]; printf("合併後數組元素:\n"); for (l = 0; l < M+N; l++) printf("%d ", c[l]); printf("\n"); return 0; }
a 數組元素: -3 6 19 26 68 100 b 數組元素: 8 10 12 22 合併後數組元素: -3 6 8 10 12 19 22 26 68 100
| 特性 | 描述 |
|---|---|
| 時間複雜度 | O(M+N)，線性掃描 |
| 空間複雜度 | O(M+N)，需額外數組存儲結果 |
| 穩定性 | 穩定（a[i] <= b[j] 保證相等元素 A 先於 B） |
| 前提條件 | 兩個輸入數組必須已排序 |
若要對單個無序數組排序，遞歸分治：
void merge_sort(int arr[], int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid+1, right);
merge(arr, left, mid, right); // 合併兩個有序子數組
}
合併兩個有序數組是歸並排序的基石，也是處理流式數據、外部排序、多路歸並的核心操作。掌握「雙指針比較、順序寫入、尾部拷貝」的標準模板，能靈活應對各類有序序列合併場景。實際開發中，C++ STL 的 std::merge、Java 的 Arrays.merge 等庫函數均基於此原理。
