归并排序 (Merge Sort)

1. 原理解析归并排序是**“分治法Divide and Conquer”的经典体现。核心思想就三个字“先分后合”**。分Divide将数组不断从中间对半劈开一直劈到每个子数组只剩下一个元素此时每个子数组天然有序。合Merge将两个有序的子数组合并成一个更大的有序数组。不断向上合并直到最终合并成一个完整的有序数组。生活中的例子整理两组已经按学号排好的试卷。我们只需要比较两组试卷最上面的一张谁小谁就先放到新桌子上直到全部放完。2. 使用场景需要极度稳定排序时间的场景归并排序的最好、最坏、平均时间复杂度都是严格的O(nlog⁡n)O(n \log n)O(nlogn)不会像快速排序那样在极端情况下退化。外部排序处理海量数据当数据量大到内存装不下时比如几百GB的日志可以把文件切成小块排好序再用归并的思想把多个有序小文件合并成大文件。Java中的对象排序Java 的Arrays.sort()在对对象Object进行排序时底层通常采用归并排序或 TimSort归并的变种因为它是一种稳定排序相等的元素排序后相对位置不变。3. 代码实战Java 实现工业级传递下标复用 temp 数组publicclassMergeSort{publicstaticvoidmergeSort(int[]arr){if(arrnull||arr.length1)return;// 准备一张和原数组一样大的“草稿纸”避免频繁开辟空间int[]tempnewint[arr.length];sort(arr,0,arr.length-1,temp);}privatestaticvoidsort(int[]arr,intleft,intright,int[]temp){if(leftright)return;// 只剩一个元素递归终止intmidleft(right-left)/2;// 防溢出的写法// 1. 分递归排好左半边和右半边sort(arr,left,mid,temp);sort(arr,mid1,right,temp);// 2. 合将两个有序部分合并merge(arr,left,mid,right,temp);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]temp){intileft;// 左边部分的起点intjmid1;// 右边部分的起点inttleft;// temp 数组的写入下标这里优化为从 left 开始方便直接抄回// 比较两边谁小谁上桌while(imidjright){if(arr[i]arr[j]){temp[t]arr[i];}else{temp[t]arr[j];}}// 兜底如果左半边有剩余直接扫进 tempwhile(imid){temp[t]arr[i];}// 兜底如果右半边有剩余直接扫进 tempwhile(jright){temp[t]arr[j];}// 将排好序的 temp 数组内容抄回原数组 arr 的对应位置intkleft;while(kright){arr[k]temp[k];k;}}}Python 实现教学切片版便于理解思想defmerge_sort(arr):# 数组为空或只有一个元素时本来就是有序的直接返回iflen(arr)1:returnarr midlen(arr)//2left_halfarr[:mid]right_halfarr[mid:]# 递归分sorted_leftmerge_sort(left_half)sorted_rightmerge_sort(right_half)# 合并returnmerge(sorted_left,sorted_right)defmerge(left,right):result[]i,j0,0whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1# 兜底操作result.extend(left[i:])result.extend(right[j:])returnresult4. 核心难点/易错点详解合并时的剩余元素处理兜底在比较合并时必然有一边会先出完牌指针越界。此时必须立刻用循环或extend把另一边剩下的元素按原顺序全部追加到临时数组的末尾。因为剩下的元素本身就是有序的不需要再比较。数组越界与拷贝范围在原数组上操作时如 Java 版temp数组拷贝回arr时下标必须严格对应当前的left到right区间不能一股脑从0抄到尾。递归的执行顺序压栈与弹栈大老板主函数会一直等待两个小弟递归调用都执行完毕并返回有序结果后才会执行最后的合并。计算机是深度优先执行的即“先一路劈到底再一层层缝合上来”。5. 复杂度分析时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)。分层数将长度为nnn的数组不断对半劈开劈到长度为 1 需要多少次答案是log⁡2n\log_2 nlog2​n次相当于一棵二叉树的深度。合每层的工作量在每一层的合并过程中不管分成多少块所有元素的总数还是nnn。合并操作本质上就是把nnn个元素分别看一眼并放进新数组需要遍历nnn次也就是O(n)O(n)O(n)。总时间层数×\times×每层操作 O(log⁡n)×O(n)O(nlog⁡n)O(\log n) \times O(n) O(n \log n)O(logn)×O(n)O(nlogn)。且无论原数组长什么样都要老老实实劈开再合并所以最好、最坏、平均时间复杂度全都是O(nlog⁡n)O(n \log n)O(nlogn)。空间复杂度O(n)O(n)O(n)。归并排序最大的痛点在于它不是原地排序。为了把两个有序数组合并必须借用一张大小为nnn的“新桌子”即代码中的temp数组。所以空间复杂度是O(n)O(n)O(n)。