一. 分治法（Divide and conquer） 分治：
将一个规模较大问题分解为规模较小的子问题，先求解这些子问题， 然后将各子问题的解合并得到原问题的解的算法思路。
递归：
直接或者间接的调用自身的算法（程序）叫递归算法（程序）。
为什么要用递归？
慎用递归？
程序具体执行步骤难理解
坏的递归大幅度提高算法复杂度
二.汉诺塔（Hanoi Tower）问题 1.问题描述 有 A,B,C 三根柱子，A 上面有 n 个盘子，我们想把 A 上面的盘子移动到 C 上，但是要满足以下三个条件：
每次只能移动一个盘子;
盘子只能从柱子顶端滑出移到下一根柱子;
盘子只能叠在比它大的盘子上。
2.解题思路
假设 n = 1，只有一个盘子，很简单，直接把它从 A 中拿出来，移到 C 上
假设 n = 2，需要借助B柱子，先将最上面的盘子移动到B柱子，再将最下面的盘子移动到C柱子上，再将B柱子上的盘子移动到C柱子上即可完成。
如果 n > 2，我们可以将除开最后一个盘子之外的所有盘子暂时充当一个整体，之后就可以采用 n = 2 的方法移动。
3.具体解决方法
n = 1 时，直接把盘子从 A 移到 C；
n > 1 时，
先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
再将最大的盘子从 A 移到 C；
再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。
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 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 //Tower类 public class Tower { String name; ArrayList<Integer> nums; public Tower(String name) { this.name = name; this.nums = new ArrayList<Integer>(); } public Tower(String name, ArrayList<Integer> nums) { this.name = name; this.nums = new ArrayList<Integer>(); for(int num : nums) { this.nums.add(num); } } public String toString() { return name + ": " + nums.toString(); } public boolean add(int num) { return this.nums.add(num); } public int remove() { return this.nums.remove(nums.size()-1); } public int size() { return nums.size(); } } //Hanoi类 package swu.xl.algorithm.code_03_17.experiment_1; public class Hanoi { //操作的次数 private static int time = 1; public static void move(Tower a, Tower b, Tower c) { //开始移动 move(a.size(),a,b,c); //移动成功后 System.out.println(a+" "+b+" "+c); } public static void move(int n, Tower a, Tower b, Tower c){ if (n == 1){ //打印当前三个圆盘的数据 System.out.println("A:"+findTowerByName(a,b,c,"A").nums+" "+"B:"+findTowerByName(a,b,c,"B").nums+" "+"C:"+findTowerByName(a,b,c,"C").nums); //找出被移除的元素 int move = a.remove(); c.add(move); //打印移动信息 System.out.println("Operation "+time+": Move "+move+" from "+a.name+" to "+c.name); time++; }else { //先把上面 n - 1 个盘子从 A 移到 B move(n-1,a,c,b); //再将最大的盘子从 A 移到 C move(1,a,b,c); //再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归） move(n-1,b,a,c); } } /** * 根据名字找到Tower * @param a * @param b * @param c * @param name * @return */ public static Tower findTowerByName(Tower a, Tower b, Tower c, String name){ if (a.name.equals(name)){ return a; }else if (b.name.equals(name)){ return b; } return c; } } //测试类 public class HanoiTest { public static void main(String[] args) { ArrayList<Integer> A_nums = new ArrayList<>(); A_nums.add(5); A_nums.add(4); A_nums.add(3); A_nums.add(2); A_nums.add(1); Tower A = new Tower("A", A_nums); Tower B = new Tower("B"); Tower C = new Tower("C"); Hanoi.move(A, B, C); } }
5.时间复杂度 确定上界，O(22 )
确定下界，Ω(22 )
确定确界：θ(22 )
三. 排列问题（Permutation）（回溯） 1.题目描述 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
2.解题思路 我们只需要按顺序枚举每一位可能出现的情况，已经选择的数字在接下来要确定的数字中不能出现。按照这种策略选取就能够做到不重不漏，把可能的全排列都枚举出来。
以数组 [1, 2, 3] 的全排列为例：
在枚举第一位的时候，有 3 种情况。
在枚举第二位的时候，前面已经出现过的数字就不能再被选取了；
在枚举第三位的时候，前面 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 //Permutation class Permutation { public static List<int[]> permute(int[] nums) { //创建一个集合用于返回 List<int[]> perms = new ArrayList<>(); //调用函数得到想要的结果 permute_recursion(nums,0,perms); return perms; } private static void permute_recursion(int[] nums, int start_index, List<int[]> perms) { int length = nums.length; //当最后一位时，将得到的一个结果加入到返回的集合中 if (start_index == length-1){ int[] perm = new int[length]; for (int i = 0; i < length; i++) { perm[i] = nums[i]; } perms.add(perm); }else { //从数组没有确定位置的数字索引开始到数组最后一位的索引 for (int i = start_index; i <= length - 1; i++) { //打好标记 swap(nums,start_index,i); //回溯 permute_recursion(nums,start_index+1,perms); //取消标记 swap(nums,start_index,i); } } } /** * nums数组中交换索引为i和j两处的元素 * @param nums * @param i * @param j */ public static void swap(int[] nums, int i, int j){ int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } //PermutationTest public class PermutationTest { public static void main(String[] args) { int[] nums = {1,2,3}; List<int[]> perms = Permutation.permute(nums); for(int[] perm : perms) { for(int element : perm) System.out.print(element + " "); System.out.println(); } } }
4.时间复杂度
根据每一层运行步骤的规律，可以找到一层的操作步骤次数是 n! 。那么可以找到 常数 c 使得当 n >= n0 时，cn! =< 总的操作次数，得到时间复杂度的下界：Ω(n!)。
四 总结
分治法(Divide and conquer)是将一个 规模较大问题分解为规模较小的子问题，先求解这些子问题
分治法的子问题通常与原问题结构和求解方法相同，可以通过递归的方法求解。
递归是一种自然的思考方式，思路清晰，易于实现。巧用递归，可以帮助解决复杂问题。但是递归算法的具体执行步骤难理解，坏的递归大幅度提高算法复杂度，所以要慎用递归。
五.力扣训练题
六.排序问题 1.归并排序 参考之前的十大排序算法
2.快速排序 在之前的十大排序算法，我们选择了数组的第一个元素作为基准点，但是仔细一想就知道，这样的选择是不合理的。所以，下面的解法是随机选取的基准点。
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 /** * 快速排序 * @param originalData * @return */ public static int[] quickSort(int[] originalData){ //存储排好序的数组 int[] sortedData = originalData.clone(); quickSortRecursion(sortedData,0,sortedData.length-1); return sortedData; } /** * 快速排序 递归 * @param sortedData * @param head * @param tail */ public static void quickSortRecursion(int[] sortedData, int head, int tail){ if (head >= tail){ return; } //产生 head 到 tail 的一个索引 int partitionIndex = head + new java.util.Random().nextInt(tail-head+1); //获得新的基准值 int pivot = partition(sortedData,head,tail,partitionIndex); //递归 quickSortRecursion(sortedData,head,pivot-1); quickSortRecursion(sortedData,pivot+1,tail); } /** * * @param sortedData * @param head * @param tail * @param partitionIndex * @return */ private static int partition(int[] sortedData, int head, int tail, int partitionIndex) { //将第一个数和我们选择的基准值交换 swap(sortedData,head,partitionIndex); //模拟指针 int left = head+1; int right = tail; while (left < right){ //从左边往右搜索大于基准值的值 while (sortedData[left] <= sortedData[head] && left < right){ left++; } //从右边往左搜索小于基准值的值 while (sortedData[right] >= sortedData[head] && left < right){ right--; } //如果还可以交换就交换 if (left < right){ swap(sortedData,left,right); } } //跳出循环 必定 left == right //找到基准值应该回去的位置 //因为left(right)不一定可以 if (sortedData[right] > sortedData[head]){ partitionIndex = right-1; swap(sortedData,head,partitionIndex); }else { partitionIndex = right; swap(sortedData,head,partitionIndex); } return partitionIndex; } /** * nums数组中交换索引为i和j两处的元素 * @param nums * @param i * @param j */ public static void swap(int[] nums, int i, int j){ int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; }
七.其他分治问题 1.第k小问题 问题描述：给定n个元素和一个整数k，1<kSn，要求找出这n个元素
■ 先排序，再取值算法复杂度? O(nlogn) （使用归并排序）
■ 类似快速排序，先随机划分，再找位置，时间复杂度? O(n) （n + n/2 + n/4 + … + 1 ）
1 2 3 4 特殊计算 T = n + n/2 + n/4 + ... + 1 ① 2T = 2n + n + n/2 + ... + 2 ② T = ② - ① = 2n-1
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 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 package swu.xl.algorithm.code_03_31.experiment_2; public class KthSmall { /** * 普通排序的方法 * @param data * @param k * @return */ public static int getKthSmallBySorting(int[] data, int k) { //排序 mergeSort(data,0,data.length-1); return data[k-1]; } /** * 归并排序 递归 * @param nums * @param start * @param end */ public static void mergeSort(int[] nums,int start,int end){ //只要划分的区间长度仍然不为1 if (start != end){ int middle = (start+end) / 2; //分 mergeSort(nums,start,middle); mergeSort(nums,middle+1,end); //治 merge(nums,start,end,middle); } } /** * 归并 * @param nums * @param start * @param end * @param middle */ public static void merge(int[] nums,int start,int end,int middle){ //模拟第一个序列的头指针 int i = start; //模拟第二个序列的头指针 int j = middle+1; //模拟临时数组的头指针 int t = 0; //创建临时数组 int[] temp = new int[end-start+1]; //从头比较两个序列，小的放入临时数组temp while (i <= middle && j <= end){ //比较大小 if (nums[i] < nums[j]){ //前一个序列 temp[t++] = nums[i++]; }else { //后一个序列 temp[t++] = nums[j++]; } } //单独处理没有处理完的第一个序列 while (i <= middle){ temp[t++] = nums[i++]; } //单独处理没有处理完的第二个序列 while (j <= end){ temp[t++] = nums[j++]; } //将临时数组的值赋值到原数组 for (int p = 0; p < temp.length; p++) { nums[start+p] = temp[p]; } } /** * 快速查找的方法 * @param a * @param k * @return */ public static int getKthSmallByDivideConquer(int[] a, int k) { //数组克隆 int[] data = a.clone(); return data[getKthSmallBYDivideConquer(data,0,data.length-1,k)]; } /** * 快速查找 递归 * @param data * @param head * @param tail * @param k * @return */ private static int getKthSmallBYDivideConquer(int[] data, int head, int tail, int k) { //递归结束的条件 if (head == tail) { return head; } else { //获得基准值的索引 int partitionIndex = randomPartition(data,head,tail); if (partitionIndex < k-1){ //说明此时找的数字比要找的数字还要小，所以向右区间寻找 return getKthSmallBYDivideConquer(data,partitionIndex+1,tail,k); }else if (partitionIndex > k-1){ //说明此时找的数字比要找的数字还要大，所以向左区间寻找 return getKthSmallBYDivideConquer(data,head,partitionIndex-1,k); }else { //恰好找到 return partitionIndex; } } } /** * 返回当前基准值在数组中的索引值 * @param data * @param head * @param tail * @return */ private static int randomPartition(int[] data, int head, int tail) { //产生一个随机数 基准值 int partitionIndex = head + new java.util.Random().nextInt(tail-head+1); //交换第一个和随机产生的索引的数字 //将基准值调成第一个元素 swap(data,head,partitionIndex); //确定模拟的头尾指针 int left = head+1; int right = tail; //左右模拟 while (left < right) { //从左边一直找，小于基准值的数的索引 while (data[left] <= data[head] && left < right){ left++; } //从右边一直找，大于基准值的数的索引 while (data[right] >= data[head] && left < right){ right--; } //如果头尾指针还没有碰头 if (left < right){ //交换位置 swap(data,left,right); } } //说明此时跳出循环 left = right //需要将基准值放回去 //需要判断left（right）此处是否可以防止 if (data[left] > data[head]){ partitionIndex = right-1; }else { partitionIndex = right; } //将基准值交换获取 swap(data,head,partitionIndex); return partitionIndex; } /** * nums数组中交换索引为i和j两处的元素 * @param nums * @param i * @param j */ public static void swap(int[] nums, int i, int j){ int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } /** * 测试程序 */ public static void main(String[] args) { int[] data = new int[]{1,2,3,4,5}; System.out.println(getKthSmallBySorting(data,2)); System.out.println(getKthSmallByDivideConquer(data,2)); } }
2.赛程安排 n(n=2k )个选手， 设计比赛日程表:
■ 每个选手必须与其他n- 1个选手各赛一次;
■ 每个选手一天只能赛-次;循环赛一共进行n-1天。
① 从这张图片我们可以看出来，子问题是对角线复制该数字，然后逆对角线add后赋值。
② 比如刚开始是[1]，第一次子问题后，[[1,2],[2,1]]，再一次子问题后，[[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,2,1]]，反反复复后即可得出结果。
③ 时间复杂度：
简单思考时间复杂度的方式：
表格总共有 n2 -> （2k )2 -> 4k 个位置需要填写。填写的过程又正好是常数阶，所以时间复杂度就是 n2 或者说 4k 。
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 package swu.xl.algorithm.code_03_31.experiment_1; public class SchedulePlanner { /** * 求解时间安排 * @param k * @return */ public static int[][] getSchedule(int k){ //获取所有的比赛人数 int n = (int) Math.pow(2,k); //创建存储数据的数组 int[][] schedule = new int[n][n]; schedule[0][0] = 1; //4->8->16，依次复制矩阵 for (int p = 1; p <= k; p++) { //开始的索引 int newStartIndex = (int) Math.pow(2,p-1); //求解范围的长度 int newLength = newStartIndex * 2; //对角线矩阵复制 matrixCopy(schedule,0,0,newStartIndex,newStartIndex,newLength/2); //邻对角线加和复制 matrixCopyAdd(schedule,0,0,0,newStartIndex,newLength/2,newLength/2); matrixCopyAdd(schedule,0,0,newStartIndex,0,newLength/2,newLength/2); } return schedule; } /** * 对角线复制 * @param matrix * @param i_s * @param j_s * @param i_d * @param j_d * @param num */ private static void matrixCopy(int[][] matrix,int i_s,int j_s,int i_d,int j_d,int num){ for (int i = 0; i < num; i++) { for (int j = 0; j < num; j++) { matrix[i_d+i][j_d+j] = matrix[i_s+i][j_s+j]; } } } /** * 邻矩阵复制（加和） * @param matrix * @param i_s * @param j_s * @param i_d * @param j_d * @param num * @param add */ private static void matrixCopyAdd(int[][] matrix,int i_s,int j_s,int i_d,int j_d,int num,int add){ for (int i = 0; i < num; i++) { for (int j = 0; j < num; j++) { matrix[i_d+i][j_d+j] = matrix[i_s+i][j_s+j] + add; } } } /** * 测试程序 * @param args */ public static void main(String[] args) { int[][] schedule = getSchedule(3); int row = schedule.length; int col = schedule[0].length; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { System.out.print(schedule[i][j]+" "); } System.out.println(""); } } }
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 42 43 44 45 46 package swu.xl.algorithm.code_04_07.experiment_1; public class Matrix { /** * 计算两个矩阵(Matrix_A（n×n）和 Matrix_B（n×n）)相乘 * @param A * @param B * @return */ public static int[][] getByDefinition(int[][] A,int[][] B){ //计算n int n = A.length; //存储结果的数组 int[][] R = new int[n][n]; //计算 R[i][j] = A[i][0] * B[0][j] + A[i][1] * B[1][j] + ... + A[i][n-1] * B[n-1][j] for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int t = 0; t < n; t++) { R[i][j] += A[i][t] * B[t][j]; } } } return R; } /** * 测试程序 */ public static void main(String[] args) { int [][] A = {{1,2},{3,4}}; int [][] B = {{1,2},{3,4}}; int[][] result = getByDefinition(A, B); for (int i = 0; i < result.length; i++) { for (int j = 0; j < result[0].length; j++) { System.out.print(result[i][j]+" "); } System.out.println(""); } } }
时间复杂度：O( n3 )
② 分块矩阵的方法求解
③ Strassen矩阵的方法求解
4.棋盘覆盖 在一一个2kx2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形
解题思路：
将棋盘划分成四份，每份四个格子。左上部分有一个特殊的方格，我们需要将其他区域也要添加特殊的方格，好转化成子问题求解。
如下图所示，添加一个L型骨牌，就可以转化成子问题。
5.最近点对
① 暴力求解法
枚举所有的情况，比较得出最小的距离。
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 /** * 最近点对问题 */ public class ClosestPair { /** * 暴力求解最近点对的距离 * @param points * @return */ public static double getByBruteForce(double[][] points){ //获得数组的长度 int n = points.length; //假设前两个点的距离最小 double minDis = getDistance(points,0,1); //封装这两个点 int[] minIndex = new int[]{0,1}; //枚举所有可能的距离 for (int i = 0; i < n-1; i++) { for (int j = i+1; j < n; j++) { //如果找到更小的距离 if(getDistance(points,i,j) < minDis){ //更换最小值 minDis = getDistance(points,i,j); //更新封装的数据 minIndex[0] = i; minIndex[1] = j; } } } //System.out.println("B坐标:"+points[minIndex[0]][0]+" "+points[minIndex[0]][1]+"|"+points[minIndex[1]][0]+" "+points[minIndex[1]][1]); return minDis; } /** * 求解二维平面两个点之间的距离 * @param points * @param i * @param j * @return */ private static double getDistance(double[][] points, int i, int j) { return Math.sqrt((points[i][0]-points[j][0])*(points[i][0]-points[j][0]) + (points[i][1]-points[j][1])*(points[i][1]-points[j][1])); } }
② 分治法
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 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 /** * 最近点对问题 */ public class ClosestPair { /** * 分治法求解最近点对的问题 * @param points * @return */ public static double getByDivideConquer(double[][] points){ //对数组进行横坐标升序 sortDoubleArray(points); //求解出最小距离的两个点的距离 int[] minIndex = getByDivideConquer(points, 0, points.length-1); return getDistance(points,minIndex[0],minIndex[1]); } /** * 二维数组按照第一列排序 * @param points */ private static void sortDoubleArray(double[][] points){ Arrays.sort(points, new Comparator<double[]>() { @Override public int compare(double[] point_a, double[] point_b) { if (point_a[0] > point_b[0]){ return 1; }else if (point_a[0] < point_b[0]){ return -1; } return 0; } }); } /** * 求解二维平面两个点之间的距离 * @param points * @param i * @param j * @return */ private static double getDistance(double[][] points, int i, int j) { return Math.sqrt((points[i][0]-points[j][0])*(points[i][0]-points[j][0]) + (points[i][1]-points[j][1])*(points[i][1]-points[j][1])); } /** * 求解排好序的最近点对 * @param points * @param head * @param tail * @return */ private static int[] getByDivideConquer(double[][] points, int head, int tail){ //开始默认的最小距离值 double minDist = getDistance(points,head,head+1); //开始默认的最小距离的两个点的坐标 int[] minIndex = new int[]{head,head+1}; //判断数据范围 if (tail-head+1 <= 4){ //数据不超过四个直接暴力求解（枚举每一种可能） for (int i = head; i <= tail - 1; i++) { for (int j = i+1; j <= tail; j++) { //如果出现了更小的情况 if (getDistance(points,i,j) < minDist){ minDist = getDistance(points,i,j); minIndex[0] = i; minIndex[1] = j; } } } }else { //数据超过四个分治求解 //求解左边最小值的两个点的坐标 以及 最小距离 int[] minIndexLeft = getByDivideConquer(points, head, (head + tail) / 2); double minDistLeft = getDistance(points, minIndexLeft[0], minIndexLeft[1]); //求解右边最小值的两个点的坐标 以及 最小距离 int[] minIndexRight = getByDivideConquer(points, (head + tail) / 2 + 1, tail); double minDistRight = getDistance(points, minIndexRight[0], minIndexRight[1]); //左右两边最小的距离 double minDistTwoSide = Math.min(minDistLeft,minDistRight); //调整当前的最小值 更换 最小值的两个点的坐标 以及 最小距离 if (minDistLeft <= minDistRight){ minDist = minDistLeft; minIndex = minIndexLeft; }else { minDist = minDistRight; minIndex = minIndexRight; } //计算中间区域的最小值 首先需要找到平分线的值（横坐标） double middleXAxis = (points[(head + tail) / 2][0] + points[(head + tail) / 2 + 1][0]) / 2; //以右边的某一个点为依据 向左找到最多六个点 //开始找的坐标的起始索引 int i = (head+tail) / 2 + 1; //首先找的索引 i 不能越界 并且 距离 平分线的 最短距离不能超过 左右两边的最小值 while (i <= tail && points[i][0] - middleXAxis <= minDistTwoSide){ //计数的变量 不超过六个 int count = 0; //向左找点 不能越界 并且 还没有找到六个点 for (int j = (head + tail) / 2; j >= head && count <= 6 ; j--){ //首先 距离 平分线的 最短距离不能超过 左右两边的最小值 //其次 找到的两个点纵坐标的差不能超过 左右两边的最小值 if (middleXAxis - points[j][0] <= minDistTwoSide && Math.abs(points[i][1] - points[j][1]) <= minDistTwoSide){ //判断这两个点之间的距离是否更小 if (getDistance(points,i,j) < minDist){ minDist = getDistance(points,i,j); minIndex[0] = i; minIndex[1] = j; } //改变找到的点数 count++; } } //继续向右找点 i++; } } return minIndex; } }
首先将所有的点按照 x 坐标的值排好序，然后在中间画一条平分线，左边的区域，右边的区域，包含左右区域的。最小值只有可能出现在这三部分。
左边的区域，右边的区域又可以像刚才那样划分，当划分到只有四个数据的时候，暴力求解，这就达到了分治的效果。
现在最困难的问题是包含左右两边区域的最小值怎么求解。我们假设，d 是左边区域的最小值和右边区域的最小值中的更小的一个。
如下图所示，如果左边有一点 p 到 右边一点的最小值 比 d 还要小。那么 点 p 的横坐标到平分线的距离一定小于 d，同理，右边的点到平分线的距离也要小于 d。
那么对于 左边的一点 p 我们是要找到右边所有 到平分线的距离要小于 d 的点吗？不是的，我们只需要找到六个点。如下图右所示，利用反证法，如果存在第七个点，在如图所示的六个区域内，最大的距离就是对角线的距离，Math.sqrt( (d/2)2 + (2d/3)2 ) = 5/6d < d。而在右边的区域中两点的最小值是大于 d 的，所以可以得出最多找六个点。这里是指对于左边区域满足条件的一点 p 都要找六个点。
时间复杂度：
分治法的递归操作每次都是均等分，所以其递归树为logn层，递归函数中的操作均为线性，所以总的时间复杂度为O(nlogn)。
可以参考这张图理解，和归并排序的理解方式类似：
