归并排序核心思想分治法Divide and Conquer分解将数组从中间分成两半解决递归地对两半分别排序合并将两个有序数组合并成一个有序数组图解示例假设待排序数组[8, 4, 5, 7, 1, 3, 6, 2]第一阶段分解递归拆分[8,4,5,7,1,3,6,2] ← 原始数组 (0-7) ↓ ┌────────────┴────────────┐ [8,4,5,7] [1,3,6,2] ← mid3分成两半 ↓ ↓ ┌────┴────┐ ┌────┴────┐ [8,4] [5,7] [1,3] [6,2] ↓ ↓ ↓ ↓ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ [8] [4] [5] [7] [1] [3] [6] [2] ← 递归终止只剩1个元素 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ [4,8] [5,7] [1,3] [2,6] ← 开始合并每层合并 ↓ ↓ ↓ ↓ [4,5,7,8] [1,2,3,6] ← 继续向上合并 ↓ ↓ [1,2,3,4,5,6,7,8] ← 最终有序数组第二阶段合并过程详解以合并[4,8]和[5,7]为例左数组 [4, 8] 右数组 [5, 7] 临时数组 [] ↑ ↑ i (left) j (mid1) 步骤1: 4 ≤ 5? 是 → temp[0] 4, i, k 左 [4, 8] 右 [5, 7] temp [4] ↑ ↑ i j 步骤2: 8 ≤ 5? 否 → temp[1] 5, j, k 左 [4, 8] 右 [5, 7] temp [4, 5] ↑ ↑ i j 步骤3: 8 ≤ 7? 否 → temp[2] 7, j, k 左 [4, 8] 右 [5, 7] temp [4, 5, 7] ↑ ↑ i (j超出右边界) 步骤4: 右数组已空将左数组剩余元素复制 temp[3] 8 temp [4, 5, 7, 8] 步骤5: 将temp复制回原数组 arr[left..right] 原数组对应位置变为 [4, 5, 7, 8]代码关键点解析代码段作用int[] temp new int[arr.length]只创建一次临时数组避免递归中重复分配内存mid (left right) / 2计算中点将数组分成两半sort(arr, left, mid, temp)递归排序左半部分sort(arr, mid1, right, temp)递归排序右半部分while (i mid j right)双指针比较取较小者放入tempwhile (i mid)/while (j right)处理剩余元素arr[left i] temp[i]将排序好的temp复制回原数组时间 空间复杂度┌─────────────┬─────────────┐ │ 时间复杂度 │ O(n log n) │ ← 每层O(n)共log n层 ├─────────────┼─────────────┤ │ 空间复杂度 │ O(n) │ ← 临时数组temp ├─────────────┼─────────────┤ │ 稳定性 │ 稳定 │ ← arr[i] arr[j] 保证相等时先取左边 └─────────────┴─────────────┘递归调用栈可视化sort(0,7) ← 第1层调用 ├─ sort(0,3) ← 第2层 │ ├─ sort(0,1)← 第3层 │ │ ├─ sort(0,0) 返回 │ │ ├─ sort(1,1) 返回 │ │ └─ merge(0,0,1) → [4,8] │ ├─ sort(2,3) │ │ ├─ sort(2,2) 返回 │ │ ├─ sort(3,3) 返回 │ │ └─ merge(2,2,3) → [5,7] │ └─ merge(0,1,3) → [4,5,7,8] └─ sort(4,7) ← 类似右半部分...核心要点先递归到底分解到单个元素再逐层向上合并代码实现publicclassMergeSort{// 归并排序入口publicstaticvoidmergeSort(int[]arr){int[]tempnewint[arr.length];sort(arr,0,arr.length-1,temp);}// 递归分解privatestaticvoidsort(int[]arr,intleft,intright,int[]temp){if(leftright){intmid(leftright)/2;sort(arr,left,mid,temp);// 左半部分sort(arr,mid1,right,temp);// 右半部分merge(arr,left,mid,right,temp);// 合并}}// 合并两个有序数组privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]temp){intileft;// 左序列指针intjmid1;// 右序列指针intk0;// 临时数组指针// 比较并放入临时数组while(imidjright){if(arr[i]arr[j]){temp[k]arr[i];}else{temp[k]arr[j];}}// 剩余元素处理while(imid)temp[k]arr[i];while(jright)temp[k]arr[j];// 复制回原数组for(i0;ik;i){arr[lefti]temp[i];}}}
归并排序（Merge Sort）
归并排序核心思想分治法Divide and Conquer分解将数组从中间分成两半解决递归地对两半分别排序合并将两个有序数组合并成一个有序数组图解示例假设待排序数组[8, 4, 5, 7, 1, 3, 6, 2]第一阶段分解递归拆分[8,4,5,7,1,3,6,2] ← 原始数组 (0-7) ↓ ┌────────────┴────────────┐ [8,4,5,7] [1,3,6,2] ← mid3分成两半 ↓ ↓ ┌────┴────┐ ┌────┴────┐ [8,4] [5,7] [1,3] [6,2] ↓ ↓ ↓ ↓ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ [8] [4] [5] [7] [1] [3] [6] [2] ← 递归终止只剩1个元素 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ [4,8] [5,7] [1,3] [2,6] ← 开始合并每层合并 ↓ ↓ ↓ ↓ [4,5,7,8] [1,2,3,6] ← 继续向上合并 ↓ ↓ [1,2,3,4,5,6,7,8] ← 最终有序数组第二阶段合并过程详解以合并[4,8]和[5,7]为例左数组 [4, 8] 右数组 [5, 7] 临时数组 [] ↑ ↑ i (left) j (mid1) 步骤1: 4 ≤ 5? 是 → temp[0] 4, i, k 左 [4, 8] 右 [5, 7] temp [4] ↑ ↑ i j 步骤2: 8 ≤ 5? 否 → temp[1] 5, j, k 左 [4, 8] 右 [5, 7] temp [4, 5] ↑ ↑ i j 步骤3: 8 ≤ 7? 否 → temp[2] 7, j, k 左 [4, 8] 右 [5, 7] temp [4, 5, 7] ↑ ↑ i (j超出右边界) 步骤4: 右数组已空将左数组剩余元素复制 temp[3] 8 temp [4, 5, 7, 8] 步骤5: 将temp复制回原数组 arr[left..right] 原数组对应位置变为 [4, 5, 7, 8]代码关键点解析代码段作用int[] temp new int[arr.length]只创建一次临时数组避免递归中重复分配内存mid (left right) / 2计算中点将数组分成两半sort(arr, left, mid, temp)递归排序左半部分sort(arr, mid1, right, temp)递归排序右半部分while (i mid j right)双指针比较取较小者放入tempwhile (i mid)/while (j right)处理剩余元素arr[left i] temp[i]将排序好的temp复制回原数组时间 空间复杂度┌─────────────┬─────────────┐ │ 时间复杂度 │ O(n log n) │ ← 每层O(n)共log n层 ├─────────────┼─────────────┤ │ 空间复杂度 │ O(n) │ ← 临时数组temp ├─────────────┼─────────────┤ │ 稳定性 │ 稳定 │ ← arr[i] arr[j] 保证相等时先取左边 └─────────────┴─────────────┘递归调用栈可视化sort(0,7) ← 第1层调用 ├─ sort(0,3) ← 第2层 │ ├─ sort(0,1)← 第3层 │ │ ├─ sort(0,0) 返回 │ │ ├─ sort(1,1) 返回 │ │ └─ merge(0,0,1) → [4,8] │ ├─ sort(2,3) │ │ ├─ sort(2,2) 返回 │ │ ├─ sort(3,3) 返回 │ │ └─ merge(2,2,3) → [5,7] │ └─ merge(0,1,3) → [4,5,7,8] └─ sort(4,7) ← 类似右半部分...核心要点先递归到底分解到单个元素再逐层向上合并代码实现publicclassMergeSort{// 归并排序入口publicstaticvoidmergeSort(int[]arr){int[]tempnewint[arr.length];sort(arr,0,arr.length-1,temp);}// 递归分解privatestaticvoidsort(int[]arr,intleft,intright,int[]temp){if(leftright){intmid(leftright)/2;sort(arr,left,mid,temp);// 左半部分sort(arr,mid1,right,temp);// 右半部分merge(arr,left,mid,right,temp);// 合并}}// 合并两个有序数组privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]temp){intileft;// 左序列指针intjmid1;// 右序列指针intk0;// 临时数组指针// 比较并放入临时数组while(imidjright){if(arr[i]arr[j]){temp[k]arr[i];}else{temp[k]arr[j];}}// 剩余元素处理while(imid)temp[k]arr[i];while(jright)temp[k]arr[j];// 复制回原数组for(i0;ik;i){arr[lefti]temp[i];}}}
