归并排序C++
时间: 2025-05-01 17:41:22 浏览: 15
### 关于C++中归并排序的实现
归并排序是一种高效的基于比较的排序算法,其时间复杂度为 \( O(n \log n) \)[^1]。它通常被设计成一种稳定排序(stable sort),这意味着如果两个元素相等,则它们在原始序列中的相对顺序会被保留到排序后的结果中。
以下是使用C++实现归并排序的一个标准版本:
```cpp
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1; // 左半部分大小
int n2 = right - mid; // 右半部分大小
std::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];
int i = 0;
int j = 0;
int 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<int>& 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); // 将两个已排序的部分合并
}
// 测试函数
void testMergeSort() {
std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};
std::cout << "Original array: ";
for(auto num : data){
std::cout << num << " ";
}
std::cout << "\n";
mergeSort(data, 0, data.size()-1);
std::cout << "Sorted array: ";
for(auto num : data){
std::cout << num << " ";
}
}
```
上述代码展示了如何通过分治策略来完成归并排序的过程。`merge()` 函数负责将两个已经排序好的子数组合并成为一个有序的整体;而 `mergeSort()` 则递归地调用自己以分割输入数组直到单个元素为止,随后再逐步将其重新组合起来形成最终的排序结果[^2]。
阅读全文
相关推荐













