C++怎么实现归并排序算法_C++排序算法与归并排序实现方法-C++-PHP中文网

C++怎么实现归并排序算法_C++排序算法与归并排序实现方法

冰火之心

发布： 2025-11-12 10:06:03

原创

950人浏览过

归并排序基于分治思想，将数组递归二分至单元素后合并为有序数组，C++实现包含分割与合并步骤，时间复杂度恒为O(n log n)，空间复杂度O(n)，稳定且适合大数据量排序。

c++怎么实现归并排序算法_c++排序算法与归并排序实现方法

归并排序是一种高效的稳定排序算法，基于分治思想。它将数组不断二分，直到每个子数组只有一个元素，再将这些子数组两两合并，合并过程中保持有序，最终得到完全有序的数组。C++中实现归并排序，关键在于递归分割和有序合并两个步骤。

归并排序的基本原理

归并排序的核心是“分而治之”：

把一个数组从中间分成左右两部分
对左右两部分分别递归调用归并排序
将排好序的两部分合并成一个有序数组

这个过程持续进行，直到整个数组有序。时间复杂度始终为O(n log n)，不受输入数据影响，空间复杂度为O(n)，需要额外数组存储临时结果。

C++中的归并排序实现

下面是一个完整的C++归并排序实现：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
using namespace std;
<p>// 合并两个有序子数组
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;</p><pre class='brush:php;toolbar:false;'>// 创建临时数组
vector<int> L(n1), R(n2);

// 复制数据到临时数组
for (int i = 0; i < n1; i++)
    L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
    R[j] = arr[mid + 1 + j];

// 合并临时数组回到arr[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
    } else {
        arr[k] = R[j];
        j++;
    }
    k++;
}

// 复制剩余元素
while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
}
while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
}

登录后复制

}

// 归并排序主函数 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); } }

// 打印数组 void printArray(const vector<int>& arr) { for (int num : arr) cout << num << " "; cout << endl; }

使用示例与测试

编写main函数来验证归并排序的效果：

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    cout << "原始数组: ";
    printArray(arr);
<pre class='brush:php;toolbar:false;'>mergeSort(arr, 0, arr.size() - 1);

cout << "排序后数组: ";
printArray(arr);

return 0;

登录后复制

}

输出结果为：

原始数组: 38 27 43 3 9 82 10
排序后数组: 3 9 10 27 38 43 82