【分治】归并排序：局部有序到整体有序

核心思想先把数组不断二分直到每个子数组只有一个元素再把相邻的有序子数组两两合并最终得到完整的有序数组。1. 问题定义给定长度为n的数组A[0...n-1]要求将数组按非递减顺序排列A[0]≤A[1]≤⋯≤A[n−1] A[0] \le A[1] \le \cdots \le A[n-1]A[0]≤A[1]≤⋯≤A[n−1]示例输入[5, 2, 8, 3, 1, 6, 4] 输出[1, 2, 3, 4, 5, 6, 8]归并排序使用分治思想最好、平均和最坏时间复杂度均为O(n log n)。2. 核心操作合并两个有序数组假设已有两个升序数组左[2, 5, 8] 右[1, 3, 6, 9]由于两个数组内部已经有序最小元素一定在两个数组当前未处理部分的首部。每次比较左右首元素把较小者写入辅助数组。三个指针i指向左区间尚未处理的第一个元素j指向右区间尚未处理的第一个元素k指向辅助数组下一个写入位置。合并步骤步骤比较取出结果数组12与11[1]22与32[1, 2]35与33[1, 2, 3]45与65[1, 2, 3, 5]58与66[1, 2, 3, 5, 6]68与98[1, 2, 3, 5, 6, 8]7左侧已空复制9[1, 2, 3, 5, 6, 8, 9]小的拿出来从数组删掉大的在数组留下继续跟后面的比两个数组共有n个元素每个元素只被处理常数次因此合并时间为O(n)。3. 分治框架归并排序包含三个阶段Divide分解从中点把数组分成左右两半Conquer解决递归地对左右两半排序Combine合并线性合并两个有序子数组。当区间长度为0或1时区间天然有序可以直接返回。是否MergeSort(A, left, right)left right?区间天然有序返回计算 mid递归排序左区间递归排序右区间合并两个有序区间当前区间有序4. 完整执行过程以[5, 2, 8, 3, 1, 6, 4]为例。分解阶段[5, 2, 8, 3, 1, 6, 4] ├── [5, 2, 8, 3] │ ├── [5, 2] │ │ ├── [5] │ │ └── [2] │ └── [8, 3] │ ├── [8] │ └── [3] └── [1, 6, 4] ├── [1, 6] │ ├── [1] │ └── [6] └── [4]合并阶段[5] [2] - [2, 5] [8] [3] - [3, 8] [2, 5] [3, 8] - [2, 3, 5, 8] [1] [6] - [1, 6] [1, 6] [4] - [1, 4, 6] [2, 3, 5, 8] [1, 4, 6] - [1, 2, 3, 4, 5, 6, 8]递归负责制造“局部有序”归并负责把两个局部有序区间变成更大的有序区间。5. 伪代码MERGE-SORT(A, left, right): if left right: return mid left (right - left) / 2 MERGE-SORT(A, left, mid) MERGE-SORT(A, mid 1, right) MERGE(A, left, mid, right) MERGE(A, left, mid, right): i left j mid 1 k left while 左右区间都还有元素: if A[i] A[j]: temp[k] A[i] i else: temp[k] A[j] j k 复制左区间剩余元素 复制右区间剩余元素 将 temp[left...right] 写回 A[left...right]6. C 语言实现下面的实现只申请一次辅助数组供整个递归过程复用。#includestdio.h#includestdlib.h/** * 合并两个有序区间 * A[left...mid] 和 A[mid1...right] */staticvoidmerge(int*A,int*temp,intleft,intmid,intright){intileft;intjmid1;intkleft;while(imidjright){if(A[i]A[j]){// 相等时优先取左侧元素保证稳定性。temp[k]A[i];}else{temp[k]A[j];}}while(imid){temp[k]A[i];}while(jright){temp[k]A[j];}for(intpleft;pright;p){A[p]temp[p];}}staticvoidmergeSortRecursive(int*A,int*temp,intleft,intright){if(leftright){return;}// 防止 left right 发生整数溢出。intmidleft(right-left)/2;mergeSortRecursive(A,temp,left,mid);mergeSortRecursive(A,temp,mid1,right);merge(A,temp,left,mid,right);}/** * 成功返回 1内存分配失败或参数无效返回 0。 */intmergeSort(int*A,intn){if(n1){return1;}if(ANULL){return0;}int*tempmalloc((size_t)n*sizeof(int));if(tempNULL){return0;}mergeSortRecursive(A,temp,0,n-1);free(temp);return1;}测试代码staticvoidprintArray(constint*A,intn){for(inti0;in;i){printf(%d%c,A[i],in-1?\n: );}}intmain(void){intarr1[]{5,2,8,3,1,6,4};intarr2[]{1};intarr3[]{9,8,7,6,5};intarr4[]{3,1,3,-2,0};intn1sizeof(arr1)/sizeof(arr1[0]);intn2sizeof(arr2)/sizeof(arr2[0]);intn3sizeof(arr3)/sizeof(arr3[0]);intn4sizeof(arr4)/sizeof(arr4[0]);if(mergeSort(arr1,n1))printArray(arr1,n1);if(mergeSort(arr2,n2))printArray(arr2,n2);if(mergeSort(arr3,n3))printArray(arr3,n3);if(mergeSort(arr4,n4))printArray(arr4,n4);return0;}输出1 2 3 4 5 6 8 1 5 6 7 8 9 -2 0 1 3 37. 正确性说明可以用数学归纳法证明。基础情况区间长度为0或1时天然有序。归纳假设假设所有长度小于n的数组都能被归并排序正确排序。归纳步骤对于长度为n的数组左右子数组长度都小于n根据归纳假设递归后左右子数组分别有序merge每次选择两个区间中尚未处理的最小元素写入辅助数组的元素始终保持非递减顺序合并结束后整个长度为n的区间有序。因此归并排序能够正确排序任意长度的数组。8. 复杂度分析时间复杂度递推式为T(n)2T(n/2)O(n) T(n) 2T(n/2) O(n)T(n)2T(n/2)O(n)每层所有合并操作共处理n个元素工作量为O(n)每次把规模减半递归树深度为O(log n)总时间为O(n) × O(log n) O(n log n)。情况时间复杂度最好情况O(n log n)平均情况O(n log n)最坏情况O(n log n)即使数组已经有序标准归并排序仍会完成全部拆分与合并。空间复杂度辅助数组O(n)递归栈O(log n)总体空间复杂度O(n)。9. 算法性质性质结论原因原地排序否标准实现需要辅助数组稳定排序是相等时优先取左侧元素最坏时间保证O(n log n)划分方式不依赖输入排列适合链表是链表合并可以通过修改指针完成适合外部排序是可以顺序读取并合并大文件稳定性若两个元素关键字相同排序后仍保持原来的相对次序则算法稳定。排序前[3a, 1, 3b] 排序后[1, 3a, 3b]合并时使用if(A[i]A[j])相等时先取左侧元素因此保持稳定。如果改为可能破坏稳定性。10. 边界情况输入输出说明[][]空数组直接返回[1][1]单元素天然有序[1, 2, 3][1, 2, 3]已排序数组[3, 2, 1][1, 2, 3]逆序数组[2, 2, 1][1, 2, 2]重复元素[-1, 3, -5][-5, -1, 3]负数11. 与其他排序算法对比算法平均时间最坏时间额外空间稳定性选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)通常O(log n)不稳定12. 与逆序对计数的关系归并排序还可以在合并阶段统计逆序对。当右侧当前元素小于左侧当前元素时左区间尚未处理的所有元素都与它构成逆序对因此可以一次增加mid−i1 mid - i 1mid−i1无序数组 ↓ 不断二分 单元素区间天然有序 ↓ 从下向上两两合并 比较左右当前元素 ├─ 左 右取左元素 └─ 左 右取右元素 ↓ 复制剩余元素 ↓ 得到更大的有序区间 ↓ 最终数组有序先递归制造局部有序再利用线性归并得到整体有序递推式为T(n)2T(n/2)O(n)所以时间复杂度为O(n log n)空间复杂度为O(n)