歸併排序是一種基於分治思想的高效排序算法，它的核心是“分而治之”——先把大問題拆成小問題解決，再把結果合併起來。和冒泡排序、選擇排序這些簡單排序算法相比，歸併排序的時間複雜度更低，適合處理較大規模的數據。
歸併排序的基本思想¶
歸併排序主要分爲兩個步驟：分解和合併。
- 分解（Divide）：
把待排序的數組從中間分成左右兩部分，然後遞歸地對每一部分重複“分解”操作，直到每一部分只有一個元素（或空數組）。這時候每個子數組已經是“有序”的了（單個元素天然有序）。
舉個例子：
假設我們要排序數組 [5, 3, 8, 6, 2, 7, 1, 4]。
第一次分解成 [5,3,8,6] 和 [2,7,1,4]；
繼續分解左半部分 [5,3,8,6] 成 [5,3] 和 [8,6]，右半部分 [2,7,1,4] 成 [2,7] 和 [1,4]；
再分解 [5,3] 成 [5] 和 [3]，[8,6] 成 [8] 和 [6]，[2,7] 成 [2] 和 [7]，[1,4] 成 [1] 和 [4]；
直到所有子數組都只有一個元素。
- 合併（Conquer）：
把兩個已排序的子數組合併成一個更大的有序數組。合併時，我們需要比較兩個子數組的元素，每次取較小的那個放入結果數組，直到其中一個子數組的元素全部處理完畢，再把剩下的元素直接放入結果數組。
比如，現在有兩個有序子數組 [3,5] 和 [6,8]，合併過程如下：
- 比較 3 和 6，取 3 放入結果；
- 比較 5 和 6，取 5 放入結果；
- 此時左子數組剩餘 6,8，右子數組已空，直接放入 6,8；
- 合併結果爲 [3,5,6,8]。
歸併排序的C++實現¶
下面我們用C++代碼實現歸併排序，主要包含兩個函數：mergeSort（遞歸分解）和 merge（合併兩個有序數組）。
步驟1：合併函數 merge¶
合併函數的作用是將兩個已排序的子數組合併成一個有序數組。
void merge(vector<int>& arr, int low, int mid, int high) {
int leftLen = mid - low + 1; // 左子數組長度
int rightLen = high - mid; // 右子數組長度
// 創建臨時數組存儲左右子數組
vector<int> left(leftLen), right(rightLen);
// 複製左子數組到臨時數組left
for (int i = 0; i < leftLen; i++) {
left[i] = arr[low + i];
}
// 複製右子數組到臨時數組right
for (int i = 0; i < rightLen; i++) {
right[i] = arr[mid + 1 + i];
}
// 合併兩個臨時數組到原數組arr
int i = 0, j = 0, k = low; // i: left指針, j: right指針, k: arr指針
while (i < leftLen && j < rightLen) {
if (left[i] <= right[j]) { // 取較小元素放入arr
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
// 處理left中剩餘的元素
while (i < leftLen) {
arr[k] = left[i];
i++;
k++;
}
// 處理right中剩餘的元素
while (j < rightLen) {
arr[k] = right[j];
j++;
k++;
}
}
步驟2：歸併排序函數 mergeSort¶
遞歸分解數組，直到子數組長度爲1，然後調用 merge 合併。
void mergeSort(vector<int>& arr, int low, int high) {
if (low < high) { // 遞歸終止條件：子數組長度爲1時停止
int mid = low + (high - low) / 2; // 避免low+high溢出，等價於 (low+high)/2
mergeSort(arr, low, mid); // 遞歸排序左半部分
mergeSort(arr, mid + 1, high); // 遞歸排序右半部分
merge(arr, low, mid, high); // 合併兩個有序子數組
}
}
步驟3：測試代碼¶
在 main 函數中調用 mergeSort 並驗證排序結果：
#include <iostream>
#include <vector>
using namespace std;
// 合併函數merge（同上）
// ...（此處省略merge函數代碼，實際使用時需完整寫出）
// 歸併排序函數mergeSort（同上）
// ...（此處省略mergeSort函數代碼，實際使用時需完整寫出）
int main() {
vector<int> arr = {5, 3, 8, 6, 2, 7, 1, 4};
int n = arr.size();
cout << "排序前的數組：";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
mergeSort(arr, 0, n - 1); // 調用歸併排序
cout << "排序後的數組：";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
示例演示：歸併排序的完整過程¶
以數組 [5, 3, 8, 6, 2, 7, 1, 4] 爲例，排序過程如下：
-
分解過程：
- 初始數組：[5, 3, 8, 6, 2, 7, 1, 4]
- 分解爲[5,3,8,6]和[2,7,1,4]
- 分解[5,3,8,6]爲[5,3]和[8,6]
- 分解[5,3]爲[5]和[3]，分解[8,6]爲[8]和[6]
- 分解[2,7,1,4]爲[2,7]和[1,4]
- 分解[2,7]爲[2]和[7]，分解[1,4]爲[1]和[4] -
合併過程：
- 合併[5]和[3]→[3,5]
- 合併[8]和[6]→[6,8]
- 合併[3,5]和[6,8]→[3,5,6,8]（左半部分排序完成）
- 合併[2]和[7]→[2,7]
- 合併[1]和[4]→[1,4]
- 合併[2,7]和[1,4]→[1,2,4,7]（右半部分排序完成）
- 最終合併[3,5,6,8]和[1,2,4,7]→[1,2,3,4,5,6,7,8]
運行代碼後，輸出結果會是排序後的數組 [1, 2, 3, 4, 5, 6, 7, 8]，驗證了算法的正確性。
總結¶
歸併排序通過“分解-合併”的步驟實現排序，時間複雜度爲 O(n log n)（分解需要log n層，每層合併n個元素），空間複雜度爲 O(n)（需要臨時數組存儲合併結果）。它是一種穩定且高效的排序算法，適合處理較大規模的數據。
通過上面的代碼和示例，你應該已經理解了歸併排序的核心邏輯。試着自己動手修改數組，看看不同輸入是否都能正確排序，加深對遞歸和合並過程的理解吧！