1. 归并排序算法原理与力扣刷题实战指南
归并排序(Merge Sort)作为分治算法的经典代表,在力扣(LeetCode)算法题库中占据着重要地位。这个算法之所以被频繁考察,是因为它完美体现了"分而治之"的编程思想,同时又是理解递归和排序算法的绝佳案例。在实际面试中,超过60%的候选人会被要求手写归并排序实现或解决相关变种问题。
1.1 分治思想的核心要义
分治算法(Divide and Conquer)的精髓可以用三个步骤概括:
- 分解:将原问题划分为若干个规模较小的子问题
- 解决:递归地解决这些子问题
- 合并:将子问题的解合并为原问题的解
关键提示:归并排序的时间复杂度稳定为O(nlogn),这是因为它每次都将数组对半分割(logn层),每层需要进行O(n)的比较操作。这种效率在需要稳定排序的场景下非常可贵。
1.2 归并排序的标准实现
以Java为例,标准的归并排序实现包含两个核心方法:
java复制// 归并排序主方法
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 防止整数溢出
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// 合并两个有序数组
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; // 保持稳定性
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
实际编码时容易踩的坑:
- 忘记处理剩余元素(第二个while循环)
- 临时数组索引计算错误
- 递归终止条件写错(应该是left < right而非left <= right)
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 力扣经典题目分类解析
2.1 基础排序类题目
题目#88 合并两个有序数组
这道题是归并排序中merge操作的直接应用。关键点在于从后向前合并,避免频繁移动元素:
python复制def merge(nums1, m, nums2, n):
p1, p2, p = m-1, n-1, m+n-1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
nums1[:p2+1] = nums2[:p2+1] # 处理剩余元素
2.2 分治策略进阶题目
题目#315 计算右侧小于当前元素的个数
这道题需要结合归并排序和逆序对统计:
java复制class Solution {
private int[] index;
private int[] temp;
private int[] tempIndex;
private int[] ans;
public List<Integer> countSmaller(int[] nums) {
this.index = new int[nums.length];
this.temp = new int[nums.length];
this.tempIndex = new int[nums.length];
this.ans = new int[n
