通过Java浅例学习分治法

   我理解的分治法的基本思想就是将一个规模很大，难以直接求解的问题，分成合适的模块，这样便于对每一个模块进行直接求解。每一个模块要在形式上和原型一致，而在规模上要比原型容易求解，这就是分治策略。基于这种策略，我们很自然的想到利用递归求解。确实，在分治法求解问题的过程中，合理的使用递归可以起到很不错的效果。下面我要分享的两个小程序就是基于分治的思想，使用递归完成的二分检索和归并排序程序。

  

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");
	}

}

 

评论

6 楼 fxsc 2010-04-04  

分治法的核心是先分再合，很多时候难点在合并结果

5 楼 zpsailor 2010-03-31  

FeiXing2008 写道

还有好多问题那样子喔

噢 ~~  什么问题呢？

4 楼 iooyoo 2010-03-31  

用递归最好首先考虑下问题规模对效率的影响，问题规模要适中，递归的核心模块逻辑也不要太大

3 楼 FeiXing2008 2010-03-31  

还有好多问题那样子喔

2 楼 zpsailor 2010-03-30  

little_bill 写道

非常好用。谢谢分享。
学习！学习！ 分治法

呵呵 客气了 我也是抱着学习的态度分享一点小程序而已，如果对你有帮助，我非常高兴

1 楼 little_bill 2010-03-30  

非常好用。谢谢分享。
学习！学习！ 分治法