分治策略（3篇）之标准分治

        第一篇：分治法之标准分治

目的：本篇博客并不具体的讨论某一个算法，而是将同类型的问题集中展示，从而对分治法有       更进一步的认识。

 

目录：

• 斐波那契数列问题
• 台阶问题
• 归并排序
• 快速排序
• BST镜像问题

问题1：斐波那契数列问题

       1)问题指出：

       斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）

       2)关键部分：

       当n>=2，求解Fn时，可以将该问题分解成 2个相同性质的子问题F(n-1)和F(n-2)。

       3)代码实现：

 

public static int Fibonacci(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}	

		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}

  （上述代码并没有做输入参数值范围检查）

问题2：台阶问题

1)问题指出：

 台阶问题是指：一个台阶总共有n级，一个人每次可以跳1级，也可以跳2级。求从最底层最高层总共有多少总跳法？

   2)关键部分

   设总跳法数目是：F(n)

   当台阶总数n = 1级时，F(n) = 1；

   当台阶总数n = 2级时，F(n) = 2；

   当台阶总数n >= 2级时,

   如果第一步跳1级，则剩下n-1级跳法总数是F(n-1);

   如果第一步跳2级，则剩下n-1级跳法总数是F(n-2);

   所以，结果是化成了2个相同性质规模更小的子问题F(n-1)和F(n-2)

         （问题转换成了问题1.）

 

 问题3：归并排序

       1）问题指出

       归并排序是指：对于一个待排序的数列，可以将该序列分成2个子数列，将这两个子数列分别排序，然后经2个已经排好序的子数列进行合并。

        2）关键部分：图片示意

                 
           

        3）代码实现：

 

public static void mergeSort(int[] data) {

		mergeSort(data, 0, data.length - 1);
	}

	private static void mergeSort(int[] data, int low, int high) {

		if (low < high) {
			int mid = (low + high) / 2;
			mergeSort(data, low, mid);
			mergeSort(data, mid + 1, high);
			merge(data, low, mid, high);
		}

	}

	// 合并
	public static void merge(int[] data, int start, int mid, int end) {
		int tmp[] = new int[end - start + 1];
		int i = start;
		int j = mid + 1;
		int k = 0;

		while (i <= mid && j <= end) {

			if (data[i] < data[j]) {
				tmp[k++] = data[i++];
			} else {
				tmp[k++] = data[j++];

			}
		}
		//拷贝左边数组的值
		while (i <= mid) {
			tmp[k] = data[i];
			k++;
			i++;
		}
		//拷贝右边数组的值
		while (j <= end) {
			tmp[k] = data[j];
			k++;
			j++;
		}

		// 重新赋值给data
		int m = 0;
		for (int n = start; n <= end; n++) {
			data[n] = tmp[m++];
		}

	}

 问题4：快速排序

     1）问题指出：

      快速排序是指：在一个待排序的序列中，指定一个分划值（比如第一个数值），运行一次分划函数使得该分划值排到序列某一位置，且该分划值左边的数值都小于等于分划值，右边的数值都大于等于该分划值。然后递归的对左边的序列使用快速排序，右边的序列使用快速排序。

      2）关键部分：图片示意

       3）代码实现

   

public static void  quickSort(int [] data,int start,int end){
		
		if(start >= end){
			return;
		}
		//分划
		int location = partition(data,start,end);
		//递归的排序
		quickSort(data,start,location-1);
		quickSort(data,location+1,end);
		
	}

    快速排序代码很是简练，尤为漂亮。

   

//分划函数
private static int partition(int [] data,int start,int end){
		
		int point =start;
		int key = data[start];
		for(int j = point+1;j<=end;j++){
			if(data[j] < key){
				point++;
				int tmp = data[j];
				data[j] = data[point];
				data[point] = tmp;
			}
		}
		//交换
		int tmp = data[start];
		data[start] = data[point];
		data[point] = tmp;
		
		
		return point;
	}

 问题5：二叉搜索树镜像问题

      1）问题指出：

       假设原始的二叉搜索树的左子树节点的值都小于根节点的值，右子树节点的值大于根节点的值，现在需要将该二叉搜索树结构换成左子树节点的值都大于根节点的值，右子树节点的值都小于根节点。

       这个很简单：改变根节点左右子树的指针，然后递归调用分别改变左右子树。

      2） 关键部分：图片示意
 

 

      3）代码实现

   

//节点结构
	class BSTNode{
		int value;
		BSTNode left;
		BSTNode right;
	}
	void reverse(BSTNode root){
		
		if(root == null){
			return;
		}
		//交换左右子节点
		BSTNode tmp;
		tmp = root.left;
		root.left = root.right;
		root.right = tmp;
		//递归调用
		reverse(root.left);
		reverse(root.right);	
	}

 
   总结：

    标准分治法，Divide-and-Conquer，一般分成三个步骤：

    步骤一：Divide ，根据某个条件将大问题分成两个规模更小同类型的问题

    步骤二：Comquer，递归调用

    步骤三：Combine，合并

 

 

 

   

 

 

 

 

 

 

 

    

 

      

评论

4 楼 十三月的 2013-04-12  

finallygo 写道

十三月的 写道

finallygo 写道

在快速排序的代码里可以加一些优化,比如在将小的数都排到左边的那个算法里,可以加一个语句

if(j == point) {
    continue;
}

这样就可以减少一些交换

没有太明白你的意思？point指针和j指针分别指向了大于key和小于key的地方，是需要交换的。不知道代码加到那里？

加在partition方法第八行的后面

呵呵 是的 你的意思是如果像第2个数字就比第1个数字小，可以添加判断从而无需“自己和自己交换”...

3 楼 finallygo 2013-04-12  

十三月的 写道

finallygo 写道

在快速排序的代码里可以加一些优化,比如在将小的数都排到左边的那个算法里,可以加一个语句

if(j == point) {
    continue;
}

这样就可以减少一些交换

没有太明白你的意思？point指针和j指针分别指向了大于key和小于key的地方，是需要交换的。不知道代码加到那里？

加在partition方法第八行的后面

2 楼 十三月的 2013-04-12  

finallygo 写道

在快速排序的代码里可以加一些优化,比如在将小的数都排到左边的那个算法里,可以加一个语句

if(j == point) {
    continue;
}

这样就可以减少一些交换

没有太明白你的意思？point指针和j指针分别指向了大于key和小于key的地方，是需要交换的。不知道代码加到那里？

1 楼 finallygo 2013-04-12  

在快速排序的代码里可以加一些优化,比如在将小的数都排到左边的那个算法里,可以加一个语句

if(j == point) {
    continue;
}

这样就可以减少一些交换