归并排序是一种基于分治思想的高效排序算法，它的核心是“分而治之”——先把大问题拆成小问题解决，再把结果合并起来。和冒泡排序、选择排序这些简单排序算法相比，归并排序的时间复杂度更低，适合处理较大规模的数据。
归并排序的基本思想¶
归并排序主要分为两个步骤：分解和合并。
- 分解（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)（需要临时数组存储合并结果）。它是一种稳定且高效的排序算法，适合处理较大规模的数据。
通过上面的代码和示例，你应该已经理解了归并排序的核心逻辑。试着自己动手修改数组，看看不同输入是否都能正确排序，加深对递归和合并过程的理解吧！