归并排序采用分治思想，先递归分割数组至单元素，再合并有序子数组，时间复杂度恒为O(n log n)，空间复杂度O(n)，稳定且适合大规模数据。
归并排序是一种典型的分治算法，通过将数组不断分割成两部分，分别排序后再合并，最终得到有序序列。它的时间复杂度稳定在 O(n log n)，适合处理大规模数据排序，且具备稳定性（相等元素的相对位置不变）。
分治策略：将一个大问题分解为多个小问题解决，再将结果合并。
归并排序分为两个阶段：
// 合并两个有序区间 [left, mid] 和 [mid+1, right] void merge(vector<int>& arr, int left, int mid, int right) { vector<int> temp(right - left + 1); // 临时数组存储合并结果 int i = left; // 左子数组指针 int j = mid + 1; // 右子数组指针 int k = 0; // 临时数组指针
// 比较并合并
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];
}}
立即学习“C++免费学习笔记（深入）”；
// 主排序函数：递归实现 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> nums = {38, 27, 43, 3, 9, 82, 10}; cout << "原始数组: "; for (int x : nums) cout << x << " "; cout << endl;
mergeSort(nums, 0, nums.size() - 1); cout << "排序后数组: "; for (int x : nums) cout << x << " "; cout << endl; return 0;
}
时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)。每次划分耗时 O(log n)，每层合并总共需要 O(n) 时间。
空间复杂度：O(n)，因为需要一个与原数组等长的临时数组用于合并操作。
稳定性：是稳定排序算法。合并过程中，当左右元素相等时优先取左边，保持了原有顺序。
适用场景：
虽然归并排序性能稳定，但仍有优化空间：
基本上就这些。归并排序结构清晰、逻辑严谨，是理解分治思想的经典范例。掌握它的实现和原理，对提升算法思维很有帮助。不复杂但容易忽略细节，比如边界处理和临时数组管理。
以上就是C++如何实现归并排序_C++分治排序算法Merge Sort的实现与分析的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
642
收藏
