C++归并排序详解（手把手教你掌握高效稳定的分治排序算法）

为什么选择归并排序？

• 时间复杂度稳定为 O(n log n)，无论最好、最坏还是平均情况。
• 是稳定排序（相等元素的相对位置不会改变）。
• 适合处理链表或外部排序（如大数据无法全部加载到内存时）。

C++归并排序完整实现

下面是一个完整的、易于理解的C++排序教程代码示例：

#include <iostream>#include <vector>using namespace std;// 合并两个已排序的子数组void merge(vector<int>& arr, int left, int mid, int right) {    // 创建临时数组    vector<int> temp(right - left + 1);    int i = left, j = mid + 1, k = 0;    // 比较左右子数组元素，按顺序放入temp    while (i <= mid && j <= right) {        if (arr[i] <= arr[j]) {            temp[k++] = arr[i++];        } else {            temp[k++] = arr[j++];        }    }    // 复制剩余元素    while (i <= mid) temp[k++] = arr[i++];    while (j <= right) temp[k++] = arr[j++];    // 将temp复制回原数组    for (int idx = 0; idx < k; idx++) {        arr[left + idx] = temp[idx];    }}// 归并排序主函数void mergeSort(vector<int>& arr, int left, int right) {    if (left < right) {        int mid = left + (right - left) / 2;        mergeSort(arr, left, mid);        // 排序左半部分        mergeSort(arr, mid + 1, right);   // 排序右半部分        merge(arr, left, mid, right);     // 合并两部分    }}// 测试函数int main() {    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};    cout << "原始数组: ";    for (int x : arr) cout << x << " ";    cout << endl;    mergeSort(arr, 0, arr.size() - 1);    cout << "排序后数组: ";    for (int x : arr) cout << x << " ";    cout << endl;    return 0;}

代码解析

1. mergeSort 函数负责递归地将数组分成两半，直到子数组只有一个元素（自然有序）。

2. merge 函数负责将两个已排序的子数组合并成一个有序数组。它使用一个临时数组来暂存结果，避免覆盖原始数据。

3. 主函数中我们创建了一个测试数组，并调用 mergeSort 进行排序，最后输出结果。

时间与空间复杂度

• 时间复杂度：O(n log n) —— 每次分解为 log n 层，每层合并耗时 O(n)。
• 空间复杂度：O(n) —— 需要额外的临时数组存储合并结果。

总结

通过本篇C++排序教程，你应该已经掌握了C++归并排序的基本原理和实现方法。归并排序作为分治算法C++的典型应用，不仅效率高，而且逻辑清晰，非常适合初学者理解递归和分治思想。

建议你动手敲一遍代码，修改测试数据，观察排序过程，加深理解。掌握归并排序后，你将为学习更复杂的算法打下坚实基础！

关键词回顾：C++归并排序、归并排序算法、C++排序教程、分治算法C++