归并排序：分治思想的经典应用

归并排序一、核心原理分治思想分把数组不断从中间拆成左右两半直到每个子数组只剩 1 个元素天然有序治把两个有序子数组合并成一个大的有序数组递归向上合并最终整个数组有序。口诀先拆分、再合并分而治之二、算法特性排序模型分治 二路归并时间复杂度最好 / 最坏 / 平均O(n logn)无最好最坏区分性能稳定空间复杂度递归版O(n)临时数组 O (logn) 递归栈稳定性稳定排序相等元素相对位置不变特点不适合海量内存外排序可做外部排序不能原地排序常规版需额外数组数据量大比插入 / 冒泡快很多三、适用场景大数据量排序要求稳定、时间复杂度严格 O (nlogn)外部排序文件超大放不下内存链表排序归并排序对链表极友好无需额外空间四、递归版归并排序cpp#include iostream #include vector using namespace std; // 合并两个有序区间 [l,mid] [mid1,r] void merge(vectorint arr, vectorint 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(vectorint arr, vectorint tmp, int l, int r) { if (l r) return; int mid (l r) / 2; mergeSortRecur(arr, tmp, l, mid); mergeSortRecur(arr, tmp, mid1, r); merge(arr, tmp, l, mid, r); } // 对外接口 void mergeSort(vectorint arr) { vectorint tmp(arr.size()); mergeSortRecur(arr, tmp, 0, arr.size()-1); } int main() { vectorint 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. 优化点子数组长度较小时比如 len15改用插入排序减少递归拆分开销提前判断如果arr[mid] arr[mid1]说明左右已经整体有序无需合并非递归迭代版归并排序消除递归栈开销。六、非递归迭代版归并排序cppvoid mergeSortIter(vectorint arr) { int n arr.size(); vectorint 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); } } }