分治算法的核心思想是**“分而治之”**将复杂问题分解为规模较小的子问题递归求解后再合并结果。分治算法核心思想分治算法遵循三个步骤分Divide将原问题分解为规模更小的子问题治Conquer递归求解子问题若问题足够小则直接求解合并Combine将子问题的解合并为原问题的解经典案例一归并排序Merge Sort归并排序是分治算法的典型应用将数组不断二分排序后合并。图解过程原始数组: [8, 4, 5, 7, 1, 3, 6, 2] 分解阶段: 合并阶段: [8,4,5,7] [1,3,6,2] → [4,5,7,8] [1,2,3,6] / \ / \ \ / [8,4] [5,7] [1,3] [6,2] → \ / | | | | \ / [8][4] [5][7] [1][3] [6][2] → [1,2,3,4,5,6,7,8]Java实现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];}}}经典案例二快速排序Quick Sort快速排序选择基准元素pivot将数组分为两部分递归排序。图解过程数组: [6, 2, 8, 4, 1, 9, 3] 选择pivot6: [2, 4, 1, 3] [6] [8, 9] ↓ ↓ [1] [2,4,3] [8] [9] ↓ [2] [4,3] ↓ [3] [4] 最终结果: [1, 2, 3, 4, 6, 8, 9]Java实现publicclassQuickSort{publicstaticvoidquickSort(int[]arr){if(arrnull||arr.length2){return;}quickSort(arr,0,arr.length-1);}publicstaticvoidquickSort(int[]arr,intlow,inthigh){if(lowhigh){intpipartition(arr,low,high);quickSort(arr,low,pi-1);// 左部分quickSort(arr,pi1,high);// 右部分}}privatestaticintpartition(int[]arr,intlow,inthigh){intpivotarr[high];// 选择最后一个元素为基准(通常选最右或中间)intilow-1;for(intjlow;jhigh;j){if(arr[j]pivot){i;// 交换inttemparr[i];arr[i]arr[j];arr[j]temp;}}// 将pivot放到正确位置inttemparr[i1];arr[i1]arr[high];arr[high]temp;returni1;}}经典案例三汉诺塔问题汉诺塔是分治算法的经典递归问题。图解3个盘子塔A 塔B 塔C [1] [] [] [2] [] [] [3] [] [] 目标: 将所有盘子从A移动到C 规则: 1. 每次移动一个盘子 2. 大盘不能压小盘Java实现仅3行核心递归publicclassHanoiTower{publicstaticvoidhanoi(intnum,charA,charB,charC){if(num1){System.out.println(第1个盘: A - C);}else{hanoi(num-1,A,C,B);// n-1个盘 A-BSystem.out.println(第num个盘: A - C);hanoi(num-1,B,A,C);// n-1个盘 B-C}}publicstaticvoidmain(String[]args){hanoi(3,A,B,C);}}分治算法适用场景算法时间复杂度空间复杂度特点归并排序O(n log n)O(n)稳定需要额外空间快速排序O(n log n) 平均O(log n)不稳定原地排序汉诺塔O(2^n)O(n)纯递归展示最近点对O(n log n)O(n)几何计算可视化工具推荐如果您想直观观察分治算法的执行过程推荐以下可视化资源VisuAlgo在线算法可视化平台支持归并排序和快速排序的逐步演示GitHub Sorting VisualizerJava编写的排序算法可视化工具包含分治算法的动态展示需要我详细解释某个具体算法的实现细节或者提供更多分治算法的应用案例如二分搜索、大整数乘法等吗
分治算法（Divide and Conquer）
发布时间：2026/6/26 19:29:01
分治算法的核心思想是**“分而治之”**将复杂问题分解为规模较小的子问题递归求解后再合并结果。分治算法核心思想分治算法遵循三个步骤分Divide将原问题分解为规模更小的子问题治Conquer递归求解子问题若问题足够小则直接求解合并Combine将子问题的解合并为原问题的解经典案例一归并排序Merge Sort归并排序是分治算法的典型应用将数组不断二分排序后合并。图解过程原始数组: [8, 4, 5, 7, 1, 3, 6, 2] 分解阶段: 合并阶段: [8,4,5,7] [1,3,6,2] → [4,5,7,8] [1,2,3,6] / \ / \ \ / [8,4] [5,7] [1,3] [6,2] → \ / | | | | \ / [8][4] [5][7] [1][3] [6][2] → [1,2,3,4,5,6,7,8]Java实现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];}}}经典案例二快速排序Quick Sort快速排序选择基准元素pivot将数组分为两部分递归排序。图解过程数组: [6, 2, 8, 4, 1, 9, 3] 选择pivot6: [2, 4, 1, 3] [6] [8, 9] ↓ ↓ [1] [2,4,3] [8] [9] ↓ [2] [4,3] ↓ [3] [4] 最终结果: [1, 2, 3, 4, 6, 8, 9]Java实现publicclassQuickSort{publicstaticvoidquickSort(int[]arr){if(arrnull||arr.length2){return;}quickSort(arr,0,arr.length-1);}publicstaticvoidquickSort(int[]arr,intlow,inthigh){if(lowhigh){intpipartition(arr,low,high);quickSort(arr,low,pi-1);// 左部分quickSort(arr,pi1,high);// 右部分}}privatestaticintpartition(int[]arr,intlow,inthigh){intpivotarr[high];// 选择最后一个元素为基准(通常选最右或中间)intilow-1;for(intjlow;jhigh;j){if(arr[j]pivot){i;// 交换inttemparr[i];arr[i]arr[j];arr[j]temp;}}// 将pivot放到正确位置inttemparr[i1];arr[i1]arr[high];arr[high]temp;returni1;}}经典案例三汉诺塔问题汉诺塔是分治算法的经典递归问题。图解3个盘子塔A 塔B 塔C [1] [] [] [2] [] [] [3] [] [] 目标: 将所有盘子从A移动到C 规则: 1. 每次移动一个盘子 2. 大盘不能压小盘Java实现仅3行核心递归publicclassHanoiTower{publicstaticvoidhanoi(intnum,charA,charB,charC){if(num1){System.out.println(第1个盘: A - C);}else{hanoi(num-1,A,C,B);// n-1个盘 A-BSystem.out.println(第num个盘: A - C);hanoi(num-1,B,A,C);// n-1个盘 B-C}}publicstaticvoidmain(String[]args){hanoi(3,A,B,C);}}分治算法适用场景算法时间复杂度空间复杂度特点归并排序O(n log n)O(n)稳定需要额外空间快速排序O(n log n) 平均O(log n)不稳定原地排序汉诺塔O(2^n)O(n)纯递归展示最近点对O(n log n)O(n)几何计算可视化工具推荐如果您想直观观察分治算法的执行过程推荐以下可视化资源VisuAlgo在线算法可视化平台支持归并排序和快速排序的逐步演示GitHub Sorting VisualizerJava编写的排序算法可视化工具包含分治算法的动态展示需要我详细解释某个具体算法的实现细节或者提供更多分治算法的应用案例如二分搜索、大整数乘法等吗
