深入浅出讲算法思想--分治法思想分析及应用
- 分治法在排序算法中的应用--归并排序
- 分治法在排序算法中的应用--快速排序(Lomuto划分、Hoare划分、随机化快排)
- 分治法在二叉树遍历中的应用--二叉查找树高度、树的遍历
- 分治法在求解"最近对"问题中的应用
- 分治法在求解凸包问题中的应用--快包算法
一、分治法在排序算法中的应用--归并排序
分治法最常用的就是将规模为n的实例划分成两个n规模为n/2的实例 。推广到一般的情况，我们可以将规模为n的实例划分为b个规模为n/b的实例。这样对于算法的运行时间存在递推式：T(n) = aT（n/b）+f（n），这个式子又被称为通用分治递推式。
我们假定递推式中的f(n)∈O(n^d)，其中d>=0，那么：
所以，对于等分的T(n) = 2T(n/2) + 1,因为a=2,b=2,d=0,并且a > b^d
则T(n) = O(n);
上面这个式子就是用来求解递推式结果的。
归并排序：(时间复杂度O(nlogn))
对于一个需要排序的数组a[0 - n-1]，先将数组一分为二a[0 - n/2-1]和a[n/2+1 - n]，对子数组排序，之后合并为一个有序数组
import java.util.Arrays;
public class Main {
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = a[j++];
}
// 把新数组中的数覆盖a数组
for (int k2 = 0; k2 < temp.length; k2++) {
a[k2 + low] = temp[k2];
}
}
public static void mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
mergeSort(a, low, mid);
// 右边
mergeSort(a, mid + 1, high);
// 左右归并
merge(a, low, mid, high);
System.out.println(Arrays.toString(a));
}
}
public static void main(String[] args) {
int[] a = {8, 3, 2, 9, 7, 1, 5, 4};
mergeSort(a, 0, a.length - 1);
System.out.println("排序结果：" + Arrays.toString(a));
}
}
归并排序在最坏情况下的键值比较次数十分接近基于比较的排序算法在理论上能够达到的最少次数。 此外快速排序和堆排序的时间复杂度也是O(nlogn)，但是相比来说，归并排序在于其稳定性
二、分治法在排序算法中的应用(JAVA)--快速排序(Lomuto划分、Hoare划分、随机化快排)
**快速排序：**时间复杂度O(nlogn)
如果说归并排序是按照元素在数组中的位置划分的话，那么快速排序就是按照元素的值进行划分。划分方法由两种，本节将主要介绍Huare划分，在深入浅出讲算法思想--减治法思想分析及应用这篇文章的第二部分中讲述了Lomuto划分用于快速查找算法，下面不再赘述，仅给出基于Lomuto的快排代码。
1. 基于Lomuto划分的快速排序算法 public class Main { static int[] a= {5, 3, 1, 9, 8, 2, 4, 7}; public static void main(String[] args) { fastsort(0, a.length-1); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } }
private static int Lomuto(int l, int r) {
int p = a[l];
int s = l;
for (int i = l+1; i <= r; i++) {
if (a[i] < p) {
s = s+1;
int temp = a[s];
a[s] = a[i];
a[i] = temp;
}
}
int temp = a[l];
a[l] = a[s];
a[s] = temp;
return s;
}
private static void fastsort(int l, int r) {
if (l < r) {
int s = Lomuto(l, r);
fastsort(l, s-1);
fastsort(s+1, r);
}
}
} 2、基于Hoare划分的快速排序
Hoare划分是一种更为复杂的划分方式，我们假设有一个数组a[0, n-1],其子数组为a[l, r](0 <= l <= r <= n-1),假定首个元素为枢轴p，下面从数组两端进行扫描，并将扫描到的元素与枢轴比较。从左到右扫描（用指针i来表示），扫描到第一个大于等于枢轴p的，停止；从右到左扫描（用指针j表示，遇到第一个小于等于枢轴的元素）。这里注意等于枢轴的元素也要进行处理，这样可以保证数组分的更加平均。如果遇到相等元素继续扫描，对于一个具有n个相同元素的数组来说，划分后得到的两个子数组长度可能为n-1和0。
两侧的扫描都停止之后，根据扫描指针是否相交会有三种情况：若 i < j，则交换a[i]与a[j]，i+1，j-1；若 i > j，交换a[p]与a[j]；若i = j，则交换a[p]与a[j]。眼尖的读者估计看出来了，后两种情况其实是一种。
下图为Hoare划分的示意图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Main {
static int[] a= {5, 3, 1, 9, 8, 2, 4, 7};
public static void main(String[] args) {
fastsort(0, a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
private static int Hoare(int l, int r) {
int p = a[l];
int i = l-1;
int j = r+1 ;
while (true) {
do {
j--;
} while (a[j] > p);
do {
i++;
} while (a[i] < p);
if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
} else
return j;
}
}
private static void fastsort(int l, int r) {
if (l < r) {
int s = Hoare(l, r);
fastsort(l, s);
fastsort(s+1, r);
}
}
}
一般来说，如果我们要考虑一个算法的实用性，我们需要讨论的不是最坏情况下的效率，而应该是平均情况下的效率。实际经过分析，快速排序平均情况下的操作仅比最优情况多执行39%的比较过程而已。所以在处理随机序列时，速度要强于归并排序和堆排序。
缺点：快速排序并非稳定性排序方式，空间复杂度为O(logn)，不及堆排序的空间复杂度O(1).
提出问题：对于数组非常小的情况下（对于大多数计算机来说，元素个数为5-15），使用插入排序会更快
解决思路1：判断元素个数，较小时采用插入排序，较大时采用快速排序。
解决思路2：不再对划分出来的较小数组排序，而是在快速排序结束后再使用插入排序的方法对整个接近有序的数组进行细微调节。
提出问题：如果我们每次都选取第一个元素为枢轴，这自然会有诸多不便，不能应对一些特殊的情况。
解决思路：随机化快速排序、三平均划分法，下面给出代码，基本思想还是划分，有兴趣的读者可以研究一下。
**3. 随机化快排：**使用随机元素作为枢轴。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42public class Main {
static int[] a= {5, 3, 1, 9, 8, 2, 4, 7};
public static void main(String[] args) {
fastsort(0, a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
private static int random_partition(int l, int r) {
int i = (int) (l + Math.random() % (r - l + 1));
int temp = a[i];
a[i] = a[r];
a[r] = temp;
return partition(l, r);
}
private static int partition(int l, int r) {
int p = a[r];
int i = l - 1;
for (int j = l; j < r; j++) {
if (a[j] <= p) {
i++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return i+1;
}
private static void fastsort(int l, int r) {
if (l < r) {
int s = random_partition(l, r);
random_partition(l, s-1);
random_partition(s+1, r);
}
}
}
**4. 三平均划分法快排：**以最左元素、最右元素、最中间元素的中位数为枢轴。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48public class Main {
static int[] a= {5, 3, 1, 9, 8, 2, 4, 7};
public static void main(String[] args) {
fastsort(0, a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
public static int mid_partition(int l, int r)
{
int range = r - l + 1;
int mid1 = (int) (l + Math.random() % range);
int mid2 = (int) (l + Math.random() % range);
int mid3 = (int) (l + Math.random() % range);
int mid = (a[mid1] < a[mid2]) ?
(a[mid2] < a[mid3] ? mid2 : (a[mid1] < a[mid3] ? mid3 : mid1)):
(a[mid1] < a[mid3] ? mid1 : (a[mid2] < a[mid3] ? mid2 : mid3));
int temp = a[mid];
a[mid] = a[r];
a[r] = temp;
return partition(l, r);
}
private static int partition(int l, int r) {
int p = a[r];
int i = l - 1;
for (int j = l; j < r; j++) {
if (a[j] <= p) {
i++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return i+1;
}
private static void fastsort(int l, int r) {
if (l < r) {
int s = mid_partition(l, r);
fastsort(l, s-1);
fastsort(s+1, r);
}
}
}
提出问题：在划分方式上Lomuto划分和Hoare划分也可以进行改进，使用诸如三路划分的方式，将数组划分3段，每段元素分别小于、等于、大于枢轴元素等等。当然，这些就仅供研究学习了，平时我们使用最简单版本的快速排序是没有任何问题的。
三、分治法在二叉树遍历中的应用--二叉查找树高度、树的遍历
二叉树本身就是由两个更小的部分组成--左子树和右子树，所以二叉树的问题非常适合用分治法来解决。
**二叉树的高度：**从叶子到根之间的最长路径。我们可以理解为根的左子树高度和右子树高度加1（加1代表根所在的层）。
定义空树的高度为-1
1
2
3
4
5
6private static int height(Node node) {
if (node == null) {
return -1;
}
return Math.max(height(node.l), height(node.r)) + 1;
}
T(n) = T(left) + T(right) + 1由递推式可得时间复杂度为O(n)
二叉树遍历：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/**
* 先序遍历
* */
private static void preorder(Node node) {
System.out.print(node.v + " ");
if (node.l != null)
preorder(node.l);
if (node.r != null)
preorder(node.r);
}
/**
* 中序遍历
* */
private static void midorder(Node node) {
if (node.l != null)
preorder(node.l);
System.out.print(node.v + " ");
if (node.r != null)
preorder(node.r);
}
/**
* 后序遍历
* */
private static void nextorder(Node node) {
if (node.l != null)
preorder(node.l);
if (node.r != null)
preorder(node.r);
System.out.print(node.v + " ");
}
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88class Node {
int v;
Node l;
Node r;
public Node(int v) {
this.v = v;
}
}
public class Main {
public static Node root;
private static int height(Node node) {
if (node == null) {
return -1;
}
return Math.max(height(node.l), height(node.r)) + 1;
}
private static boolean insert(Node node) {
if (root == null) {
root = node;
return true;
}
Node cur = root;
while (cur != null) {
if (node.v > cur.v) {
if (cur.r == null) {
cur.r = node;
return true;
}
cur = cur.r;
} else {
if (cur.l == null) {
cur.l = node;
return true;
}
cur = cur.l;
}
}
return false;
}
/**
* 先序遍历
* */
private static void preorder(Node node) {
System.out.print(node.v + " ");
if (node.l != null)
preorder(node.l);
if (node.r != null)
preorder(node.r);
}
/**
* 中序遍历
* */
private static void midorder(Node node) {
if (node.l != null)
preorder(node.l);
System.out.print(node.v + " ");
if (node.r != null)
preorder(node.r);
}
/**
* 后序遍历
* */
private static void nextorder(Node node) {
if (node.l != null)
preorder(node.l);
if (node.r != null)
preorder(node.r);
System.out.print(node.v + " ");
}
public static void main(String[] args) {
/**
* 插入
* */
insert(new Node(20));
insert(new Node(10));
insert(new Node(30));
/**
* 前序遍历
* */
preorder(root);
nextorder(root);
midorder(root);
System.out.println(height(root));
}
}
当然，并非所有关于二叉树的算法都需要遍历两颗子树，诸如二叉树的查找、插入、删除操作只需要遍历其中一棵，有兴趣的读者可以参考深入浅出讲算法思想--减治法思想分析及应用这篇文章的第三部分。
关于二叉树感兴趣的朋友还可以继续学习一篇文章搞定面试中的二叉树题目(java实现)
四、分治法在求解“最近对”问题中的应用
最近对问题在蛮力法中有过讲解，时间复杂度为O(n^2)，下面将会采用分治法讲解这类问题，时间复杂度会降到O(nlogn)
我们将笛卡尔平面上n>1个点构成的集合称为P。若2<= n <= 3时，我们1可以通过蛮力法求解。但当n>3时，采用分治法或许是个更好的选择。假设这些点是按照x轴、y轴升序排列的，可以找出点集在x轴方向上的中位数m，做一条垂直x轴的分割线，由此点将点集划分为左右两个大小为n/2的子集P1和P2，之后通过递归求解出在子集中的最近对距离d1，d2，最后找出d=max{d1，d2}。
但是！！！不巧的是，我们忽略了一个问题，如果距离最近的两个点刚好分别在两个子集中，那么d就不是所有点对的最小距离。我们需要在每次合并子问题结果时，要加以判断是否存在这样的点对。方法是：只考虑以分割线为对称轴、宽度为2d的垂直带中的的点，因为其他点对的距离都是大于d的。
这里给出一个优化，当我们在垂直带中找到一个点p，只需要考虑p之后的5个点即可。
这是因为：如果我们在垂直带中找到p-p'两点的距离小于p，由于我们的序列时经过排序的，所以p'一定在p之后，且两点在y轴上的距离一定是小于d的（根据勾股定理，两点之间的距离如果小于d，那么x轴分量和y轴分量都是小于d的，反之，不可能存在这个点）。所以在几何学上，p'的位置一定在下图中的淡黄色矩形区域。而矩形区域内一般只能包含少量的候选点，这个数量最大为6（根据鸽巢定理）。图中6个红色点为极端的临界情况。我们将d * 2d的矩形划分为d/2 * 2d/3的6块区域，如果超过6个点，假设为7，那么一定会出现某个小矩形中有两个点，这两个点的最大距离为图中红线距离5/6d<d，这和d的意义不符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Point {
double x;
double y;
Point (double x, double y) {
this.x = x;
this.y = y;
}
}
public class Main {
static Point[] point;
static Point[] minP = new Point[2];
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
int n = in.nextInt();
point = new Point[n];
// for (int i = 0; i < n; i++) {
// int a = in.nextInt();
// int b = in.nextInt();
// point[i] = new Point(a, b);
// }
point[0] = new Point(1,3);
point[1] = new Point(2,1);
point[2] = new Point(3,5);
point[3] = new Point(4,4);
point[4] = new Point(5,2);
Arrays.sort(point,0, n, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return (int) (o1.x - o2.x);
}
});
System.out.println(point.length);
double minD = closestPoint(0, point.length-1);
for (int i = 0; i < 2; i++) {
System.out.println(minP[i].x + "," + minP[i].y);
}
System.out.println(minD);
}
private static double closestPoint(int low, int high) {
Point[] temp1 = new Point[2];
Point[] temp2 = new Point[2];
Point[] p = new Point[high - low + 1];
double d, d1, d2, d3;
int index = 0;
if (high - low == 1) {
minP[0] = new Point(point[low].x, point[low].y);
minP[1] = new Point(point[high].x, point[high].y);
return distance(point[low], point[high]);
}
if (high - low == 2) {
d1 = distance(point[low], point[low+1]);
d2 = distance(point[low+1], point[high]);
d3 = distance(point[low], point[high]);
if ((d1 <= d2) && (d1 <= d3)) {
minP[0] = new Point(point[low].x, point[low].y);
minP[1] = new Point(point[low+1].x, point[low+1].y);
return d1;
} else if (d2 <= d3) {
minP[0] = new Point(point[low+1].x, point[low+1].y);
minP[1] = new Point(point[high].x, point[high].y);
return d2;
} else {
minP[0] = new Point(point[low].x, point[low].y);
minP[1] = new Point(point[high].x, point[high].y);
return d3;
}
}
int mid = (low + high) / 2;
d1 = closestPoint(low, mid);
temp1[0] = minP[0];
temp1[1] = minP[1];
d2 = closestPoint(mid+ 1, high);
temp2[0] = minP[0];
temp2[1] = minP[1];
if (d1 < d2) {
d = d1;
minP[0] = temp1[0];
minP[1] = temp1[1];
} else {
d = d2;
minP[0] = temp2[0];
minP[1] = temp2[1];
}
for (int i = mid;i>=low && (point[mid].x - point[i].x) < d; i--) {
p[index++] = point[i];
}
for (int i = mid+1;i<=high && (point[i].x - point[mid].x) < d; i++) {
p[index++] = point[i];
}
Arrays.sort(p, 0, index, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return (int) (o1.y - o2.y);
}
});
for (int i = 0; i < index-1; i++) {
for (int j = i+1; j < index; j++) {
if ((p[j].y - p[i].y) >= d) {
break;
} else {
d3 = distance(p[i], p[j]);
if (d3 < d) {
minP[0] = new Point(p[i].x, p[i].y);
minP[1] = new Point(p[j].x, p[j].y);
}
}
}
}
return d;
}
private static double distance(Point p1, Point p2) {
return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
}
}
Input：
5
Output：
4.0,4.0 3.0,5.0 1.4142135623730951
五、分治法在求解凸包问题中的应用--快包算法
分治法在求解凸包问题中的应用（JAVA）
之前写过一篇深入浅出讲算法思想--蛮力法思想分析及应用其中的第二部分讲述了蛮力求解凸包问题的思想，没有基础的读者最好先去阅读以下。
这里用分治法来求解凸包问题，由于这个算法和快速排序十分相似，因此又被称为“快包”。
在平面上有n>1个点构成的集合，定义为S，为简化思考，假定这些点按照x轴、y轴升序排列。有一个几何事实就是，最左边的一个点p1和最右边的一个点pn一定是集合的凸包顶点。我们连接p1与pn，这条直线将所有的点分成了两个子集合S1，S2。如果p1，p2，p3构成一个逆时针回路，我们称p3为与直线p1-p2的左侧；反之，称为p3为与直线p1-p2的右侧。另外S集合中位于p1-p2直线上的点，肯定不是凸包的顶点，直接忽略不考虑。
S的凸包边界是有上下两条多角形链条组成的，“上”边界称为上包，上包由p1、S1（如果S1不为空）中的一些点、p2为端点组成，“下”边界称为下包，下包由p1、S2（如果S2不为空）中的一些点、p2为端点组成。上下端点用同样的方法构造而成，采用分治法思路更为清晰。下面以上包为例，分析所谓的快包算法：
由于一些下标不好表示，这里截取了《算法设计与分析基础》中的文字讲解部分。
知道了原来，我们该如何实现呢？假设我们有三个点p1（x1, x1）, p2(x2, y2)，p3(x3, y3)，这三点围成的三角形的面积可以用下面的公式计算：
当且仅当p3位于直线p1-p2左侧时，该表达式符号为正。
和快速排序一样，该算法的最差时间复杂度为O(n^2)，但是平均效率好很多！
下面的代码在精度上由于采用double类型，但是没有做判断上的处理，比如比较大小的时候，所以对于高精度的数据并不适用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Point {
double x;
double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
}
public class Main {
static Point[] point;
static double[] s = new double[6];
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
int n = in.nextInt();
point = new Point[n];
// for (int i = 0; i < n; i++) {
// int a = in.nextInt();
// int b = in.nextInt();
// point[i] = new Point(a, b);
// }
point[0] = new Point(1,3);
point[1] = new Point(2,1);
point[2] = new Point(3,5);
point[3] = new Point(4,4);
point[4] = new Point(5,2);
point[5] = new Point(3,2);
Arrays.sort(point,0, n, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
if (o1.x - o2.x == 0) {
return (int) (o1.y - o2.y);
}
return (int) (o1.x - o2.x);
}
});
System.out.println(point[0].x + "," + point[0].y);
hull(1, n-1,point[0],point[0]);
}
private static void hull(int l,int r,Point p1,Point p2){
int x=l;
int i=l-1,j=r+1;
/**
* 找出距离直线p1-p2最远的点p3
* */
for (int k = l; k <= r; k++){
if (s[x] - s[k] <= 0) {
x=k;
}
}
Point p3 = point[x];
/**
* p1-p3左侧的点
* */
for (int k = l; k <= r; k++) {
s[++i] = cross(point[k], p1, p3);
if (s[i] > 0) {
Point temp = point[i];
point[i] = point[k];
point[k] = temp;
} else {
i--;
}
}
/**
* 直线p3-p2右侧的点
* */
for (int k=r;k>=l;k--) {
s[--j]=cross(point[k], p3, p2);
if (s[j] > 0) {
Point temp = point[j];
point[j] = point[k];
point[k] = temp;
} else {
j++;
}
}
/**
* 分治，并中序输出
* */
if (l <= i) {
hull(l, i, p1, p3);
}
System.out.println(p3.x + "," + p3.y);
if (j <= r) {
hull(j, r, p3, p2);
}
}
private static double cross (Point a, Point b, Point c) {
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
}