分治算法是五大常用算法，很多人在平时学习中可能只是知道分治算法，但是可能并没有系统的学习分治算法，本篇就带你较为全面的去认识和了解分治算法@mikechen
什么是分治算法？
分治算法，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
下面我简要介绍下刚才提到的“分治”以及“分治”。
- 分(Divide)：递归解决较小的问题(到终止层或者可以解决的时候停下)；
- 治(Conquer)：递归求解，如果问题够小直接求解；
- 合并(Combine)：将子问题的解构建父类问题。
分治算法思想步骤
分治法算法，大致分为如下三个步骤：
1）分解
将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
2）求解
若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。
3）合并
将各个子问题的解合并为原问题的解。
分治算法经典例子
1.快速排序
快排也是分治的一个实例：快排每一趟会选定一个数，将比这个数小的放左面，比这个数大的放右面。
然后递归分治求解两个子区间，当然快排因为在分的时候就做了很多工作，当全部分到最底层的时候这个序列的值就是排序完的值，这是一种分而治之的体现。
如下动图所示：
代码如下：
public class QuickSort {
public static void quickSort(int[] arr,int low,int high) {
int p,i,j,temp;
if(low >= high) {
return;
}
//p就是基准数,这里就是每个数组的第一个
p = arr[low];
i = low;
j = high;
while(i < j) {
//右边当发现小于p的值时停止循环
while(arr[j] >= p && i < j) {
j--;
}
//这里一定是右边开始，上下这两个循环不能调换（下面有解析，可以先想想）
//左边当发现大于p的值时停止循环
while(arr[i] <= p && i < j) {
i++;
}
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
arr[low] = arr[i];//这里的arr[i]一定是停小于p的，经过i、j交换后i处的值一定是小于p的(j先走)
arr[i] = p;
quickSort(arr,low,j-1); //对左边快排
quickSort(arr,j+1,high); //对右边快排
}
public static void main(String[] args) {
int[] arr = new int[] {9,4,6,8,3,10,4,6};
quickSort(arr,0,arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
2.二分查找
二分查找是典型的分治算法的应用。
算法流程：
1）选择一个标志 i 将集合分为二个子集合；
2）判断标志 L(i) 是否能与要查找的值 des 相等，相等则直接返回；
3）否则判断 L(i) 与 des 的大小；
4）基于判断的结果决定下步是向左查找还是向右查找；
5）递归继续上面的步骤。
代码如下：
public int searchInsert(int[] nums, int target) {
if(nums[0]>=target)return 0;//剪枝
if(nums[nums.length-1]==target)return nums.length-1;//剪枝
if(nums[nums.length-1]<target)return nums.length;
int left=0,right=nums.length-1;
while (left<right) {
int mid=(left+right)/2;
if(nums[mid]==target)
return mid;
else if (nums[mid]>target) {
right=mid;
}
else {
left=mid+1;
}
}
return left;
}
3.归并排序
快排在分的时候做了很多工作，而归并就是相反，归并在分的时候按照数量均匀分，而合并时候已经是两两有序的进行合并。
归并排序算法流程：
- 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的；
- 然后再把有序子序列合并为整体有序序列，即先划分为两个部分；
- 最后进行合并。
代码如下：
import java.util.Arrays;
/**
* 归并排序
*/
public class MergeSort {
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(Comparable[] arr, int l, int mid, int r) {
Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) { // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j - l];
j++;
} else if (j > r) { // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i - l];
i++;
} else if (aux[i - l].compareTo(aux[j - l]) < 0) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i - l];
i++;
} else { // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j - l];
j++;
}
}
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) / 2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if (arr[mid].compareTo(arr[mid + 1]) > 0)
merge(arr, l, mid, r);
}
public static void sort(Comparable[] arr) {
int n = arr.length;
sort(arr, 0, n - 1);
}
// 测试MergeSort
public static void main(String[] args) {
int N = 20;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
//打印数组
SortTestHelper.printArray(arr);
}
}
关于mikechen
mikechen睿哥，10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。