1.概念
分而治之是一种很古老但很实用的策略，简单的说就是将一个较大的力量打碎分成小的力量，这样每个小的力量都能够被轻易击破。在现实应用中，分而治之往往是阻止小力量联合起来的策略。在战国时期，秦国就使用了“连横”的策略来破坏“合纵”，本质上就是对“分而治之”这种策略的应用。
1.1 三个步骤
- 分解：将原问题分解成若干个子问题。
- 解决：递归求解各自子问题，如果子问题足够小，直接求解。
- 合并：合并这些子问题的解，即可得到原问题的结果。
总结就是，分治法就是把一个难以解决的大问题，分解为若干的小问题，每个击破得出结果，然后把这些子问题的解合并，就是大问题的解。递归是彰显分治法优势的利器
2.分治法的实际使用场景
2.1 二分查找
问题场景举例：猜数字游戏，一个人在自己手心上写上一个1~10的数字，然后让另外一个人猜，她只能回答大了还是小了，另外一个人采用什么办法，可以尽快猜中？
二分查找算法的实现思想是：
它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。
动画演示：
java代码实现
class Main {
public static void main(String[] args) {
int[] w = new int[] { 2, 6, 7, 4, 10, 3 };
int index = binarySearch(w, 6);
System.out.println("位置为：" + index);
}
/**
* 二分查找
*
* @Title: binarySearch
* @Description:
* @author: itbird
* @date 2022年10月20日 下午5:06:52
* @param w
* @param i
* void 时间复杂度: O(logN) 空间复杂度: O(1)
*/
private static int binarySearch(int[] w, int i) {
if (w == null || w.length == 0) {
return -1;
}
int low = 0, high = w.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (w[mid] == i) {
return mid;
} else if (w[mid] < i) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}2.2 归并排序
问题描述：对于数组排序。
归并排序的原理：归并排序是一种分治的思想，将大问题拆解成为小问题，将一个大的数组先拆分成几个小的数组，然后再一点点的合并。
归并排序的步骤：
- 将无序的数组，分为两个规模相等的数组
- 继续分组，这里明显要采用递归的做法，直到分成的数组大小为1，那么一个数字，我们知道不用排序了
- 这时是将无序的数组，分为了若干的
单数字的数组，接下来最重要的步骤，就是合并了 - 如何将两个数组合并为一个有序数组？相信各位想到的办法肯定很多，这里介绍一种最简单的，就是逐个遍历这两个数组中的元素，对比过程中，逐渐然后加入新的数组中。
动画：
Java代码实现：
import java.util.Arrays;
class Main {
public static void main(String[] args) {
int[] w = new int[] { 2, 6, 7, 4, 10, 3 };
mergeSort(w, 0, w.length - 1);
System.out.println(Arrays.toString(w));
}
/**
* 归并排序
*
* @Title: mergeSort
* @Description:
* @author: itbird
* @date 2022年10月20日 下午8:08:23
* @param w
* void 时间复杂度: O(nlogn) 空间复杂度: O(N)
* @param j
* @param i
*/
private static void mergeSort(int[] w, int i, int j) {
if (i < j) {
int mid = (i + j) / 2;
mergeSort(w, i, mid);
mergeSort(w, mid + 1, j);
merge(w, i, mid, j);
}
}
/**
* 将两个数组合并
*
* @Title: merge
* @Description:
* @author: itbird
* @date 2022年10月20日 下午8:10:25
* @param w
* @param i
* @param mid
* @param j
* void 时间复杂度: O(N) 空间复杂度: O(N)
*/
private static void merge(int[] w, int left, int mid, int right) {
int[] res = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (w[i] < w[j]) {
res[k++] = w[i++];
} else {
res[k++] = w[j++];
}
}
while (i <= mid) {
res[k++] = w[i++];
}
while (j <= right) {
res[k++] = w[j++];
}
System.arraycopy(res, 0, w, left, res.length);
}
}2.3 快速排序
问题描述：对于数组排序。
快速排序的原理：快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的步骤：
- 从数组中找到一个基准值
- 以基准值对数组进行双指针遍历，一个指针从前往后，一个从后往前，左边找到比基准值大的，右边找到比基准值小的，然后交换他们，然后指针继续移动，直到指针相遇，指针相遇之后，将基准值赋值为当前指针位置
- 以当前指针位置为中心，分为两个数组，进行上述步骤，直到所有遍历完成
动画：
Java代码实现：
import java.util.Arrays;
class Main {
public static void main(String[] args) {
int[] w = new int[] { 2, 6, 7, 4, 10, 3 };
quickSort(w, 0, w.length - 1);
System.out.println(Arrays.toString(w));
}
/**
* 快速排序
*
* @Title: quickSort
* @Description:
* @author: itbird
* @date 2022年10月21日 下午2:25:02
* @param w
* @param l
* @param r
* void 时间复杂度: O(nlogn) 空间复杂度: O(logn)
*/
private static void quickSort(int[] w, int l, int r) {
if (l > r) {
return;
}
int i = l, j = r;
int k = w[l];
while (i < j) {
while (i < j && w[j] > k) {
j--;
}
if (i < j) {
w[i++] = w[j];
}
while (i < j && w[i] < k) {
i++;
}
if (i < j) {
w[j--] = w[i];
}
}
w[i] = k;
quickSort(w, i + 1, r);
quickSort(w, l, i - 1);
}
}2.4 归并排序与快速排序的区别
相同点：
- 利用分治思想
- 具体实现都用递归
不同点：
- 先分解再合并：归并排序先递归分解到最小粒度，然后从小粒度开始合并排序，自下而上的合并排序；
- 边分解边排序：快速排序每次分解都实现整体上有序，即参照值左侧的数都小于参照值，右侧的大于参照值；是自上而下的排序；
- 归并排序不是原地排序，因为两个有序数组的合并一定需要额外的空间协助才能合并；
- 快速排序是原地排序，原地排序指的是空间复杂度为O(1)；
- 归并排序每次将数组一分为二，快排每次将数组一分为三
