分治算法总结

分治法学习总结

分治法是我们经常用到的算法，合理利用分治算法可以使我们更好的解决问题。我们在使用二分查找、归并排序的时候都要用到分治算法。下面我将从三个方面介绍分治算法，方便我们更好的了解和学习分治算法。
1.分治算法介绍
2.分治算法应用分析
3.分治算法例题分析

1.分治算法介绍

1.基本概念

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

2.解题思路

1、原问题可以分解为多个子问题
这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
2、原问题在分解过程中，递归地求解子问题
由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。
3、在求解并得到各个子问题的解后
应能够采用某种方式、方法合并或构造出原问题的解。
不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想 。

2.分治算法应用分析

先让我们通过一个简单的二分查找来理解分治算法的基本思路。

public static int commonBinarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;         //定义middle
        
        if(key < arr[low] || key > arr[high] || low > high){
            return -1;              
        }
        
        while(low <= high){
            middle = (low + high) / 2;
            if(arr[middle] > key){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(arr[middle] < key){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                return middle;
            }
        }
        
        return -1;      //最后仍然没有找到，则返回-1
    }

首先先在排序的数组找到中间值，定义我们的中间值，找到就返回，找不到就在符合条件的子问题继续二分，直到满足边界条件退出循环。

1.归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.

分治图解.jpg 分治图解.jpg

public static int[] sort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            sort(a,low,mid);
            sort(a,mid+1,high);
            //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }
     
    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high-low+1];
        int i= low;
        int j = mid+1;
        int k=0;
        // 把较小的数先移到新数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组 
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }

2.快速排序

给定数组int[]a={7,5,3,2,9,10,8,4,6,1};
第1步：找基准值
所谓的基准值，顾名思义就是以它为基准进行比大小。通常来说，我们选取数组的第一个数为基准值。在数组a里基准值就是7.
第2步：比大小
先从数组的最右边开始往左边找比基准值小的第一个数，然后从数组的最左边开始往右找比基准值大的第一个数。那么为什么要这么找呢？因为现在我们要把数组从小到大排序，所以要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。
那么在数组a里，从左往右找，第一个比7大的数就是9，我们把它的坐标记为i；从右往左找，第一个比7小的数就是1，我们把它的坐标记为j。
第3步：交换
找到之后，如果这个时候i<j，那么就交换这两个数，因为i=4,j=9，符合条件，将9和1进行交换。现在数组变成了int[]a={7,5,3,2,1,10,8,4,6,9};
如果j>=i，那么不做处理
为什么还要判断i和j的大小呢？就像第二步说的，我们要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。所以如果i<j的话，交换就达到目的了，如果i>=j，比基准值小的数就在基准值的左边，比基准值大的数已经在基准值的右边了，这时候就没必要交换了。
第4步：继续查找
在i<j的前提下，继续向右查找比基准值大的数，往左找比基准值小的数，然后交换。
在我们的例子中，10和6、8和4都符合交换的条件，所以数组就变成了
int[]a={7,5,3,2,1,6,4,8,10,9};这时候i=6,j=7
第5步：交换基准值到合适的位置
当查找继续进行，这时候i=j=6，已经不满足继续查找和交换的条件了，那么我们应该怎么办呢？答案就是把a[6]和基准值交换，因为i=j的时候说明已经到了一个分界线的位置，分界线左边的数比基准值小，分界线右边的数比基准值大，而这个分界线就是我们的基准值，所以把它和a[i]交换，这时候数组就变成：
int[]a={4,5,3,2,1,6,7,8,10,9};
第6步：重复
对基准值左右两边的两个子数组重复前面五个步骤直至排序完成。

分治算法例题分析

最大子序和