归并排序：分治思想的经典应用
归并排序
一、核心原理
分治思想
- 分：把数组不断从中间拆成左右两半，直到每个子数组只剩 1 个元素（天然有序）；
- 治：把两个有序子数组合并成一个大的有序数组；
- 递归向上合并，最终整个数组有序。
口诀：先拆分、再合并，分而治之
二、算法特性
- 排序模型：分治 + 二路归并
- 时间复杂度
- 最好 / 最坏 / 平均：O(n logn)
- 无最好最坏区分，性能稳定
- 空间复杂度
- 递归版：O(n)临时数组 + O (logn) 递归栈
- 稳定性：稳定排序（相等元素相对位置不变）
- 特点
- 不适合海量内存外排序（可做外部排序）
- 不能原地排序（常规版需额外数组）
- 数据量大比插入 / 冒泡快很多
三、适用场景
- 大数据量排序
- 要求稳定、时间复杂度严格 O (nlogn)
- 外部排序（文件超大放不下内存）
- 链表排序（归并排序对链表极友好，无需额外空间）
四、递归版归并排序
cpp
#include <iostream> #include <vector> using namespace std; // 合并两个有序区间 [l,mid] [mid+1,r] void merge(vector<int>& arr, vector<int>& tmp, int l, int mid, int r) { int i = l; // 左区间起点 int j = mid + 1; // 右区间起点 int k = l; // 临时数组起点 // 逐个比较，小的先放入tmp while (i <= mid && j <= r) { if (arr[i] <= arr[j]) tmp[k++] = arr[i++]; else tmp[k++] = arr[j++]; } // 拷贝左区间剩余 while (i <= mid) tmp[k++] = arr[i++]; // 拷贝右区间剩余 while (j <= r) tmp[k++] = arr[j++]; // 临时数组 拷贝回 原数组 for (int p = l; p <= r; ++p) arr[p] = tmp[p]; } // 递归分治 void mergeSortRecur(vector<int>& arr, vector<int>& tmp, int l, int r) { if (l >= r) return; int mid = (l + r) / 2; mergeSortRecur(arr, tmp, l, mid); mergeSortRecur(arr, tmp, mid+1, r); merge(arr, tmp, l, mid, r); } // 对外接口 void mergeSort(vector<int>& arr) { vector<int> tmp(arr.size()); mergeSortRecur(arr, tmp, 0, arr.size()-1); } int main() { vector<int> a = {5,2,4,6,1,3}; mergeSort(a); for (int x : a) cout << x << " "; return 0; }五、知识点扩展
1. 为什么是稳定排序？
合并时判断用arr[i] <= arr[j]，相等先取左边，相对位置不变 → 稳定。
2. 缺点
- 需要额外 O (n) 临时数组，空间开销大
- 递归有栈开销
3. 优化点
- 子数组长度较小时（比如 len<=15），改用插入排序，减少递归拆分开销；
- 提前判断：如果
arr[mid] <= arr[mid+1]，说明左右已经整体有序，无需合并； - 非递归迭代版归并排序，消除递归栈开销。
六、非递归（迭代版）归并排序
cpp
void mergeSortIter(vector<int>& arr) { int n = arr.size(); vector<int> tmp(n); // 步长：从1开始，每次翻倍 for (int len = 1; len < n; len <<= 1) { // 每两组合并一次 for (int l = 0; l + len < n; l += len * 2) { int mid = l + len - 1; int r = min(l + 2 * len - 1, n - 1); merge(arr, tmp, l, mid, r); } } }