C++归并排序实现与分治算法解析

归并排序采用分治策略，将数组递归二分至单元素后合并，C++实现稳定高效，时间复杂度恒为O(n log n)，适合大规模数据排序。

归并排序（Merge Sort）是一种典型的分治算法，它将数组不断二分，直到每个子数组只有一个元素，再逐步合并这些有序的子数组，最终得到一个完整的有序序列。C++中实现归并排序结构清晰、效率稳定，时间复杂度始终为O(n log n)，适合处理大规模数据排序。

分治策略的基本思想

归并排序基于“分而治之”的策略，分为三个步骤：

• 分解： 将数组从中间分成两个子数组，递归地对它们进行排序。
• 解决： 当子数组长度为1时，自然有序，递归终止。
• 合并： 将两个已排序的子数组合并成一个有序数组。

MergeSort 的 C++ 实现

以下是完整的 C++ 归并排序代码实现，包含递归分解与合并操作：

#include 
#include 
void merge(std::vector& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector 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];

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k++] = L[i++];
    } else {
        arr[k++] = R[j++];
    }
}

while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(std::vector& 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() {
std::vector arr = {38, 27, 43, 3, 9, 82, 10};
std::cout << "原始数组: ";
for (int x : arr) std::cout << x << " ";
std::cout << "\n";
mergeSort(arr, 0, arr.size() - 1);

std::cout << "排序后数组: ";
for (int x : arr) std::cout << x << " ";
std::cout << "\n";

return 0;
}

关键细节说明

上述代码有几个需要注意的地方：

• mid 的计算： 使用 left + (right - left)/2 防止整数溢出，比直接 (left+right)/2 更安全。
• 临时数组 L 和 R： 存储左右两部分数据，避免在原数组上直接比较造成混乱。
• 合并逻辑： 比较左右子数组当前元素，较小者放入原数组，指针前移。任一子数组遍历完后，剩余元素直接复制。
• 稳定性： 归并排序是稳定排序，相等元素的相对位置不会改变，这得益于合并时使用了 <= 判断。

性能与适用场景

归并排序的优势在于：

• 最坏、平均、最好情况时间复杂度都是 O(n log n)。
• 适用于链表排序（无需随机访问）和外部排序（数据量大无法全部加载内存）。

缺点是需要额外的 O(n) 空间存储临时数组，空间开销较大。但在大多数应用场景中，其稳定性和高效性使其成为可靠选择。

基本上就这些。归并排序结构清晰，理解分治思想后，代码实现自然水到渠成。不复杂但容易忽略边界处理和临时数组管理。写一次，调一遍，基本就能掌握。