算法图解第四章笔记：快速排序1（java版）

分而治之（D&C）一种著名的递归式问题的解决方法。

案例：农场主分地问题：

要求：要将这块地均匀分成方块，且分出的方块尽可能大。

步骤：（1）找出基线条件，这种条件必须尽可能的简单

​ （2）不断将问题分解（或者说是缩小规模），直到符合基线条件

这个案例很有意思，而且后面的顿悟时刻：为何不对余下的那一块小块地使用相同的算法呢？这正是递归的核心思想啊。

另一个小例子：

​ 给定一个数组：2，4，6

​ 需要将这些数字相加，并返回结果。使用循环很容易。

public static int sum(int[] arr){
		int total = 0;
		for(int i = 0;i < arr.length ; i++){
			total += arr[i];
		}
		return total;
	}

如何用递归完成这种任务呢？

第一步：找出基线条件。最简单的数组：不包含任何元素或只包含元素，这样计算总和非常容易。

第二步：每次递归调用都必须离空数组更进一步。

那么如何缩小问题的规模呢？给sum传递的数组更短。

练习：

4.1:实现前述sum函数

分析：这个问题基线条件比较清晰，不太清晰的点其实是递归条件，如何让数组离空数组更近一步呢？一开始我想的是，把数组截取，让数组长度每次调用都减一。其实这样想就有点偏差了，因为让数组变成空数组，其实并不是真的让数组逐渐的变为空数组，其实一直都是原来的数组，只不过每次调用的元素都是数组中的不同元素。下面的代码可能会更加帮助理解递归条件：

代码如下：

/*
	 * 练习4.1：利用递归求和：
	 * 		基线条件： 最简单的数组：不包含任何元素或者只包含一个元素
	 * 		递归条件： 给函数传递的数组越来越短
	 * 
	 */
	public static int sum_1(int[] arr,int n){
            //基线条件
            if( n == 0 ){
                return arr[n];
           }else{
               return arr[n] + sum_1(arr,n-1);
		}
	
	}

4.2：编写一个递归函数来计算列表包含的元素数

分析：乍一看这个问题和4.1不太一样，但是如果数组中每个元素的值都是1的话，是不是这时候求数组的和，得到的就是列表中所包含的元素数。所以只需要把上述的代码稍做修改即可。

代码如下：

/*
	 * 练习4.2：编写函数来计算列表所包含的元素数
	 * 
	 */
	public static int countNumbers(int[] arr,int n){
            //判断数组是否为空
            if(arr.length == 0){
			return 0;
		}
              //基线条件
		else if(n == 0){
			return 1;
		}else{
			return 1 + countNumbers(arr, n-1);
		}

	}

4.3：找出列表中最大的数字

分析：这个问题就比前两个深化一些了，要找出列表中的最大值，其实有很多方法。如果用递归去做，其实还是要考虑基线条件和递归条件。和前两个问题类似，递归条件还是想让传入的数组的长度原来越短，换句话说就是，想要比较的元素数越来越少。这里可以把一个数组分割成为两个，通过数组的下标做判断。左数组找出一个最大值，右数组找一个最大值，再进行比较，返回大的那个。

代码如下：

public static int findMax(int[] arr,int leftIndex,int rightIndex){
            //基线条件
		if(leftIndex == rightIndex){
			return arr[leftIndex];
		}
             //这种方式求得mid不会溢出
		int mid = leftIndex + (rightIndex -leftIndex)/2;
		int maxLeft = findMax(arr,leftIndex,mid);
		int maxRight = findMax(arr,mid+1,rightIndex);
		
		return Math.max(maxLeft, maxRight); 
	}
}

我的测试数组为2，4，6，8

所得到的输出为：