我理解的分治法的基本思想就是将一个规模很大,难以直接求解的问题,分成合适的模块,这样便于对每一个模块进行直接求解。每一个模块要在形式上和原型一致,而在规模上要比原型容易求解,这就是分治策略。基于这种策略,我们很自然的想到利用递归求解。确实,在分治法求解问题的过程中,合理的使用递归可以起到很不错的效果。下面我要分享的两个小程序就是基于分治的思想,使用递归完成的二分检索和归并排序程序。
package fenzhi;
/**
* 使用分治法的思想查找最大值
*
* @author Administrator
*
*/
public class FindMax {
// 返回最大值的方法
public int returnMax(int array[]) {
int length = array.length;
int first;
int second;
if (length == 1) {
return array[0];
} else if (length == 2) {
return Math.max(array[0], array[1]);
} else if (length < 1) {
return 0;
} else { //这里将一个数组一分为二,然后各个求解
first = length / 2;
second = length - length / 2;
int firstArray[] = new int[first];
int secondArray[] = new int[second];
for (int i = 0; i < first; i++) {
firstArray[i] = array[i];
}
for (int j = first; j < length; j++) {
secondArray[j - first] = array[j];
}
return Math.max(returnMax(firstArray), returnMax(secondArray));
}
}
public static void main(String[] args) {
FindMax findMax = new FindMax();
int array[] = { 5, 12, 1, 36, 9, 2, 14, 30, 21, 56,80,12,33};
long start = System.currentTimeMillis();
int max = findMax.returnMax(array);
long end = System.currentTimeMillis();
System.out.println("这个数组中的最大值是:" + max);
System.out.println("本次查找耗时: " + (end - start) + " ms");
}
}
上面的程序使用二分法查找一个数组的最大值,这是一个简单的程序,但我认为已经能很好的解释分治法的思想了。下面一个程序将通过一个归并排序来进一步说明。这些都只是简单的应用,但是理解了这个思想后,可以在很多实际的应用中让我们的程序变得更加有效。
package fenzhi;
//归并排序
public class MergerSort {
public int[] sort(int array[]) throws Exception {
int newArray[];
int length = array.length;
int first, second;
newArray = new int[length];
if (length == 1) {
return array;
} else if (length == 2) {
newArray[0] = Math.min(array[0], array[1]);
newArray[1] = Math.max(array[0], array[1]);
return newArray;
} else {// 这里用到了分治法的思想,将一个数组一分为二
first = length / 2;
second = length - length / 2;
int firstMark = 0;//用来标记第一个数组取到的下标
int secondMark = 0;//用来标记第二个数组取到的下标
int mark = 0;
int firstArray[] = new int[first];
int secondArray[] = new int[second];
for (int i = 0; i < first; i++) {
firstArray[i] = array[i];
}
for (int j = first; j < length; j++) {
secondArray[j - first] = array[j];
}
firstArray = this.sort(firstArray);
secondArray = this.sort(secondArray);
while (mark < length) {
if (firstMark < first && secondMark < second) {
if (firstArray[firstMark] <= secondArray[secondMark]) {
newArray[mark] = firstArray[firstMark];
firstMark++;
} else {
newArray[mark] = secondArray[secondMark];
secondMark++;
}
} else if (firstMark < first && secondMark >= second) {
newArray[mark] = firstArray[firstMark];
firstMark++;
} else if (firstMark >= first && secondMark < second) {
newArray[mark] = secondArray[secondMark];
secondMark++;
} else {
throw new Exception("error");
}
mark++;
}
}
return newArray;
}
public static void main(String[] args) {
MergerSort mergerSort = new MergerSort();
int array[] = { 5, 12, 1, 36, 9, 2, 14, 30, 21, 56, 80, 12, 33 };
long start = System.currentTimeMillis();
long end = System.currentTimeMillis();
try {
array = mergerSort.sort(array);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("排序后的数组为:");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + "\t");
}
System.out.println("本次查找耗时: " + (end - start) + " ms");
}
}
分享到:
相关推荐
使用java编写 用分治法实现对于平面上最近点对的查找 使用Swing作为界面
资源位分治法求最近点对,包含几种算法,以及图形界面,是一套完整的工程。全部为java实现。
分治法的基本思想 将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。
java 快速排序 折半查找的界面实现 (递归与分治法)
主要是算法的课程设计,对分治法进行详细的分析和讲解,同时用java语言对其进行实现
本项目是由java实现的大矩阵相乘Strassen算法。采用的是分治法的算法。
用的分治法的思想,凸包顶点正好可以构成循环,感觉比较新颖,就是不断顺时针旋转,按照书上那个公式不断找出左边的点和顶点,不断存入到数组中,最后的输出刚好是顺时针的输出,创建了好几个数组,其中还有一个三维数组,...
算法设计与分析课内实验——分治法求众数。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)
关于分治法的算法结课论文,讲述了分治法与递归的联系与区别。分治法是解题思路,而递归是实现的方法,可用递归,也可用非递归
数据结构的分治法求解最大值,数据结构的分治法求解最大值
分治法求最大最小值
分治法实现矩阵相乘
分治法-中位数 第一行: n,为x和y数组的元素个数 第二行: x数组的n个数,用空格分隔 第三行: y数组的n个数,用空格分隔
分治法求01背包问题c语言 已调通
分治法求最大值和最小值 实验报告
算法设计与分析中最大子段和问题的蛮力法、分治法和动态规划法
在一个2^k×2^k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有...
与C++编写的分治法排序程序,使用c++语言编写,实现了数组的分治法排序
分治法求最近点对问题,要求:1. 对于平面上给定的N个点,给出所有点对的最短距离,即,输入是平面上的N个点,输出是N点中具有最短距离的两点。 2. 要求随机生成N个点的平面坐标,应用蛮力法编程计算出所有点对的...
这个是根据算法分析与设计写出来的用分治法和蛮力法求解最近对问题的代码,可以直接运行。手动输入产生点的个数,输出蛮力和分治的时间。嗯,分治法我没有给出最近对的参数,有兴趣的可以自己试着写写。