1. 归并排序算法原理与实现归并排序Merge Sort是一种典型的分治算法其核心思想是将原始数组不断二分直到每个子数组只剩一个元素然后逐步合并这些有序子数组。这个算法在力扣LeetCode等编程题库中经常出现因为它很好地体现了分治思想并且时间复杂度稳定在O(nlogn)。1.1 分治策略解析归并排序的分治过程可以分为三个步骤分解将当前区间一分为二解决递归排序两个子区间合并将两个已排序的子区间合并这种分而治之的策略使得归并排序在处理大规模数据时效率很高。在实际编码实现时我们通常会使用递归来实现这个分治过程。1.2 合并操作详解合并两个已排序数组是归并排序的核心操作。具体步骤是创建一个临时数组存放合并结果使用双指针分别遍历两个子数组比较指针所指元素将较小的放入临时数组当一个子数组遍历完后将另一个子数组剩余元素全部放入临时数组这个合并过程的时间复杂度是O(n)因为每个元素只需要被比较和移动一次。2. 力扣中的归并排序题目解析力扣上有许多题目都可以使用归并排序的思想来解决。下面我们分析几个典型题目。2.1 力扣88题合并两个有序数组这是最基础的归并排序应用。题目要求将两个有序数组合并到一个数组中。解题要点从后向前合并可以避免频繁移动元素注意处理其中一个数组提前遍历完的情况不需要返回值直接修改nums1数组提示这道题的关键在于理解题目允许修改nums1数组并且nums1有足够的空间容纳合并后的结果。2.2 力扣1699题两人之间的通话次数这道题虽然表面看起来与排序无关但使用归并排序的思想可以高效解决。解题思路将通话记录按时间排序使用双指针统计特定两人之间的通话次数合并统计结果这种解法的时间复杂度主要取决于排序过程因此归并排序的O(nlogn)特性在这里很有优势。3. 归并排序的代码实现3.1 C实现示例void mergeSort(vectorint nums, int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(nums, l, mid); mergeSort(nums, mid 1, r); merge(nums, l, mid, r); } void merge(vectorint nums, int l, int mid, int r) { vectorint temp(r - l 1); int i l, j mid 1, k 0; while (i mid j r) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } while (i mid) temp[k] nums[i]; while (j r) temp[k] nums[j]; for (int p 0; p k; p) { nums[l p] temp[p]; } }3.2 Java实现要点在Java中实现归并排序时需要注意数组边界处理要格外小心临时数组的创建会带来额外的空间开销对于对象数组比较操作需要实现Comparable接口或提供Comparator4. 归并排序的优化技巧4.1 小数组使用插入排序当子数组规模较小时通常小于15插入排序的实际效率可能高于归并排序。因此可以设置一个阈值当子数组大小小于阈值时改用插入排序。4.2 避免频繁内存分配在递归过程中频繁创建临时数组会带来性能开销。可以在排序开始前一次性分配足够大的临时数组然后在递归过程中重复使用。4.3 判断是否已有序在合并前可以先判断两个子数组是否已经有序。如果前一个子数组的最大值小于等于后一个子数组的最小值则可以跳过合并步骤。5. 归并排序在力扣Hot100中的应用力扣Hot100中有多道题目可以使用归并排序的思想解决。例如链表排序力扣148题使用归并排序可以在O(nlogn)时间内完成链表排序数组中的逆序对力扣315题通过修改归并排序的过程可以高效统计逆序对数量排序链表力扣148题归并排序是链表排序的最佳选择注意在处理链表问题时归并排序的空间复杂度可以优化到O(1)这是它相对于快速排序的一个优势。6. 归并排序的常见错误与调试技巧6.1 数组越界问题在实现归并排序时数组下标计算容易出错。常见错误包括中点计算不正确应该使用l (r - l) / 2而不是(l r) / 2避免整数溢出递归终止条件错误应该是l r而不是l r合并时指针越界忘记检查指针是否超出子数组范围6.2 性能问题排查如果实现的归并排序性能不理想可以检查是否进行了不必要的数组拷贝递归深度是否过大可以考虑改用迭代实现临时数组的创建是否过于频繁7. 归并排序与其他排序算法的比较7.1 与快速排序对比时间复杂度两者平均都是O(nlogn)但归并排序更稳定空间复杂度归并排序需要O(n)额外空间快速排序是原地排序稳定性归并排序是稳定的快速排序通常不稳定7.2 与堆排序对比堆排序也是O(nlogn)但不稳定归并排序在外部排序中更有优势堆排序的空间复杂度是O(1)在实际应用中归并排序特别适合以下场景需要稳定排序时处理链表排序时进行外部排序时8. 归并排序的变种与应用8.1 多路归并排序标准的归并排序是二路归并但也可以扩展到多路归并。这在外部排序中特别有用比如处理大规模数据时。8.2 自底向上的归并排序除了递归实现还可以使用迭代的方式自底向上实现归并排序。这种实现方式避免了递归带来的栈开销代码稍复杂但性能可能更好特别适合链表排序8.3 外部归并排序当数据量太大无法全部装入内存时可以使用外部归并排序将数据分成多个块每个块单独排序然后逐步合并这些已排序的块这是数据库等系统中常用的排序方法9. 力扣刷题中的归并排序技巧在力扣刷题时掌握以下技巧可以更好地应用归并排序识别可以使用分治策略的问题注意边界条件的处理合理选择递归或迭代实现对于链表问题优先考虑归并排序在需要稳定排序时选择归并排序我个人的经验是在解决涉及排序、合并、逆序对等关键词的题目时首先考虑归并排序是否适用。特别是在处理链表相关问题时归并排序往往是首选算法。 
长河君 · 2026/10/29 13:26:41 · 阅读 1.2k 归并排序算法原理与力扣刷题实战
1. 归并排序算法原理与实现归并排序Merge Sort是一种典型的分治算法其核心思想是将原始数组不断二分直到每个子数组只剩一个元素然后逐步合并这些有序子数组。这个算法在力扣LeetCode等编程题库中经常出现因为它很好地体现了分治思想并且时间复杂度稳定在O(nlogn)。1.1 分治策略解析归并排序的分治过程可以分为三个步骤分解将当前区间一分为二解决递归排序两个子区间合并将两个已排序的子区间合并这种分而治之的策略使得归并排序在处理大规模数据时效率很高。在实际编码实现时我们通常会使用递归来实现这个分治过程。1.2 合并操作详解合并两个已排序数组是归并排序的核心操作。具体步骤是创建一个临时数组存放合并结果使用双指针分别遍历两个子数组比较指针所指元素将较小的放入临时数组当一个子数组遍历完后将另一个子数组剩余元素全部放入临时数组这个合并过程的时间复杂度是O(n)因为每个元素只需要被比较和移动一次。2. 力扣中的归并排序题目解析力扣上有许多题目都可以使用归并排序的思想来解决。下面我们分析几个典型题目。2.1 力扣88题合并两个有序数组这是最基础的归并排序应用。题目要求将两个有序数组合并到一个数组中。解题要点从后向前合并可以避免频繁移动元素注意处理其中一个数组提前遍历完的情况不需要返回值直接修改nums1数组提示这道题的关键在于理解题目允许修改nums1数组并且nums1有足够的空间容纳合并后的结果。2.2 力扣1699题两人之间的通话次数这道题虽然表面看起来与排序无关但使用归并排序的思想可以高效解决。解题思路将通话记录按时间排序使用双指针统计特定两人之间的通话次数合并统计结果这种解法的时间复杂度主要取决于排序过程因此归并排序的O(nlogn)特性在这里很有优势。3. 归并排序的代码实现3.1 C实现示例void mergeSort(vectorint nums, int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(nums, l, mid); mergeSort(nums, mid 1, r); merge(nums, l, mid, r); } void merge(vectorint nums, int l, int mid, int r) { vectorint temp(r - l 1); int i l, j mid 1, k 0; while (i mid j r) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } while (i mid) temp[k] nums[i]; while (j r) temp[k] nums[j]; for (int p 0; p k; p) { nums[l p] temp[p]; } }3.2 Java实现要点在Java中实现归并排序时需要注意数组边界处理要格外小心临时数组的创建会带来额外的空间开销对于对象数组比较操作需要实现Comparable接口或提供Comparator4. 归并排序的优化技巧4.1 小数组使用插入排序当子数组规模较小时通常小于15插入排序的实际效率可能高于归并排序。因此可以设置一个阈值当子数组大小小于阈值时改用插入排序。4.2 避免频繁内存分配在递归过程中频繁创建临时数组会带来性能开销。可以在排序开始前一次性分配足够大的临时数组然后在递归过程中重复使用。4.3 判断是否已有序在合并前可以先判断两个子数组是否已经有序。如果前一个子数组的最大值小于等于后一个子数组的最小值则可以跳过合并步骤。5. 归并排序在力扣Hot100中的应用力扣Hot100中有多道题目可以使用归并排序的思想解决。例如链表排序力扣148题使用归并排序可以在O(nlogn)时间内完成链表排序数组中的逆序对力扣315题通过修改归并排序的过程可以高效统计逆序对数量排序链表力扣148题归并排序是链表排序的最佳选择注意在处理链表问题时归并排序的空间复杂度可以优化到O(1)这是它相对于快速排序的一个优势。6. 归并排序的常见错误与调试技巧6.1 数组越界问题在实现归并排序时数组下标计算容易出错。常见错误包括中点计算不正确应该使用l (r - l) / 2而不是(l r) / 2避免整数溢出递归终止条件错误应该是l r而不是l r合并时指针越界忘记检查指针是否超出子数组范围6.2 性能问题排查如果实现的归并排序性能不理想可以检查是否进行了不必要的数组拷贝递归深度是否过大可以考虑改用迭代实现临时数组的创建是否过于频繁7. 归并排序与其他排序算法的比较7.1 与快速排序对比时间复杂度两者平均都是O(nlogn)但归并排序更稳定空间复杂度归并排序需要O(n)额外空间快速排序是原地排序稳定性归并排序是稳定的快速排序通常不稳定7.2 与堆排序对比堆排序也是O(nlogn)但不稳定归并排序在外部排序中更有优势堆排序的空间复杂度是O(1)在实际应用中归并排序特别适合以下场景需要稳定排序时处理链表排序时进行外部排序时8. 归并排序的变种与应用8.1 多路归并排序标准的归并排序是二路归并但也可以扩展到多路归并。这在外部排序中特别有用比如处理大规模数据时。8.2 自底向上的归并排序除了递归实现还可以使用迭代的方式自底向上实现归并排序。这种实现方式避免了递归带来的栈开销代码稍复杂但性能可能更好特别适合链表排序8.3 外部归并排序当数据量太大无法全部装入内存时可以使用外部归并排序将数据分成多个块每个块单独排序然后逐步合并这些已排序的块这是数据库等系统中常用的排序方法9. 力扣刷题中的归并排序技巧在力扣刷题时掌握以下技巧可以更好地应用归并排序识别可以使用分治策略的问题注意边界条件的处理合理选择递归或迭代实现对于链表问题优先考虑归并排序在需要稳定排序时选择归并排序我个人的经验是在解决涉及排序、合并、逆序对等关键词的题目时首先考虑归并排序是否适用。特别是在处理链表相关问题时归并排序往往是首选算法。