算法篇的文章主要为对"图解算法"一书的记录与总结

分而治之

分而治之(divide and conquer， D&C),一种著名的 **递归式** 解决问题的方法.快速排序中便使用到了该方法;D&C的工作原理：    - 找出简单的基线条件；    - 确定如何缩小问题的规模，使其符合基线条件复制代码

分而治之的例子

java实现

/**     * 获取符合条件的正方形的边长     *     * @param height 矩形的长度     * @param width  矩形的宽度     * @return     */    public int getValue(int height, int width) {        //获取矩形长对宽的取余        int remainder = height % width;        if (remainder ==0) {//这便是递归的基线条件，成立则退出递归，避免死循环            //说明此时长度为宽度的整数n倍,宽度即为符合正方形的边长            return width;        }        //递归调用,以最长边为新的矩形的长度        return getValue(width,remainder);    }复制代码

快速排序案例

对数组Integer[] array = new Integer[]{5, 4, 1, 5, 7, 6, 2, 3};进行从小到大排序;

用分而治之的理念，先确认出递归的基准条件；对排序算法来说，最简单的数组就是空数组或者只包含一个元素的数组，因为这种情况下，只需要返回原数组，根本不用进行排序。所以基线条件就是:数组为空或者只包含一个元素。

代码实现

/**     * 快速排序     *     * @param array 需要进行排序的数组     * @param start 需要进行排序的数组的起始索引     * @param end   需要进行排序的数组的结束索引     */    private void quickSort(Integer[] array, int start, int end) {        if (start < end) {            //获取进行分区的基准值索引            int pivotIndex = partition(array, start, end);            Log.d("yy", "基准值索引：" + pivotIndex);            //对基准左右2个分区再次进行递归排序            quickSort(array, start, pivotIndex - 1);            quickSort(array, pivotIndex + 1, end);        }    }    /**     * 获取基准值索引位置     *     * @param array     * @param start     * @param end     * @return     */    int partition(Integer[] array, int start, int end) {        // 基准值大小（ pivot）        int pivot = array[start];        if (start < end) {            while (start < end) {                //从右往左查找比pivot基准值小的数                while (start < end && array[end] >= pivot) {                    end--;                }                array[start] = array[end];                //从左往右查找比pivot基准值小的数                while (start < end && array[start] <= pivot) {                    start++;                }                array[end] = array[start];            }        }        array[start] = pivot;        return start;    }复制代码

图解