c++怎么实现归并排序算法_c++归并排序的实现与性能分析

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

c++怎么实现归并排序算法_c++归并排序的实现与性能分析

2025-10-30

浏览次数：次

返回列表

归并排序通过递归将数组二分至单元素后合并，实现稳定排序。C++代码使用临时数组合并子序列，保证相同元素相对位置不变，时间复杂度始终为O(n log n)，空间复杂度O(n)。适用于需稳定性和一致性能的场景，可结合插入排序或改用自底向上方式优化。

c++怎么实现归并排序算法_c++归并排序的实现与性能分析

归并排序是一种基于分治思想的稳定排序算法，通过将数组不断二分，直到每个子数组只有一个元素，再逐层合并，最终得到有序序列。C++中实现归并排序不仅逻辑清晰，而且便于理解递归与数组操作。下面详细介绍其实现方式和性能特点。

归并排序的基本实现

归并排序的核心是“分”和“合”。分的过程使用递归将数组一分为二；合的过程则是将两个已排序的子数组合并成一个有序数组。

以下是C++中的典型实现：

#include <iostream>
#include <vector>
using namespace std;
<p>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;</p><pre class='brush:php;toolbar:false;'>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++];

for (int p = 0; p < k; p++) {
    arr[left + p] = temp[p];
}

}

void mergeSort(vector& arr, int left, int right) { if (left >= right) return; 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};
    mergeSort(arr, 0, arr.size() - 1);
    for (int x : arr) cout << x << " ";
    return 0;
}