算法设计与分析案例代码总结(一)：分治法

分治法

代码是用java写的封装在类中的函数，具体调用测试还需要实现

求集合的全排列

实现原理：
 对于不重复的一个序列集合进行全排列，以{a,b,c}为例：
p{a,b,c}={a}p{b,c}+{b}p{a,c}+{c}p{a,b}
 也就是说，对于n个元素的全排列，就是
p(a1,a2,…,an}={a1}p{a2,a3,…,an}+{a2}p{a1,a3,…,an}+……+{an}p{a1,a2,…an-1}；
 同理，对于上面表达式中的仍然可以细分，层层分解。

public class FullPermutation {


    public  void Perm(char[] perm ,int  k ,int m){
        int i;
        if(k == m)
        {
            for(i = 0;i < m; i++ ) System.out.print(perm[i]+" ");
            System.out.println("\n");
            return;
        }

        for(i = k; i<m;i++)
        {
            Swap(perm,k,i);
            Perm(perm, k+1, m);
            Swap(perm,i, k);
        }
    }
    public void Swap(char[]perm,int a ,int b)
    {
        char n = perm[a];
        perm[a] = perm[b];
        perm[b] = n;
    }

整数的划分问题

实现原理：
q(n,m)=1; n=1|m=1

q(n,m)=q(n,n); n<m

q(n,n)=1+q(n,m-1); n=m

q(n,m)=q(n-m,m)+q(n,m-1); m<n

public class Integerdivision {
    public int equationCount(int n,int m){
        if(n == 1||m == 1)
            return 1;
        else if(n < m)
            return equationCount(n,n);
        else if(n == m)
            return 1+equationCount(n,n-1);
        else
            return equationCount(n,m-1)+equationCount(n-m,m);
    }
}

二分查找

实现原理：很简单，这里不再多说

public class Binarysearch {
    public int search(int a[], int x, int low,int high)//x表示要查找的元素
    {
        if(low>high)
            return -1;
        int middle = (low+high)/2;
        if(x == a[middle])
            return middle;
        else if(x>a[middle])
            return search(a, x, middle+1, high);
        else
            return search(a,x,low,middle-1);
    }
}

归并排序

实现原理：
 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
 基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

 可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

public class Mergesort {
    private void memeryArray(int[] a, int first, int mid, int last,int[] temp)
    {
        int i = first,j = mid + 1;
        int m = mid,n = last;
        int k = 0;
        while(i <= m && j <= n)
        {
            if(a[i] < a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }
        while(i <= m)
            temp[k++] = a[i++];
        while(j <= n)
            temp[k++] = a[j++];
        for(i = 0; i < k; i++)
            a[first+i] = temp[i];
    }
    public void mergesort(int[] a, int first, int last, int[] temp)
    {
        if(first < last)
        {
            int mid = (first+last)/2;
            mergesort(a,first,mid,temp);
            mergesort(a,mid+1,last,temp);
            memeryArray(a,first,mid,last,temp);
        }
    }
}

快速排序

实现原理：
 快速排序算法的基本思想是：先找一个基准元素进行一趟快速排序，使得该基准元素左边的所有数据都比它小，右边的数据都比他大，然后按照此方法，对左右两边的数据分别进行快速排序，整个过程可以递归进行，以此达到整个数组变成有序序列。
代码实现：

public class QuickSort {
    public void quickSort(int[] arr,int low,int high)//arr表示传入的数组，low，high分别表示要排序的起始位置和终止位置(注意下标从0开始)
    {
        int mid;
        if(low<high){
            mid = partition(arr,low,high); //基准位置
            quickSort(arr,low,mid-1); //对左子序列进行快排
            quickSort(arr,mid+1,high); //对右子序列进行快排
        }
    }
    /**
     * 划分序列，找到基准元素的位置
     */
    private int partition(int[] arr,int low,int high)
    {
        int i = low;
        int j = high;
        int temp = arr[low];
        while(i < j)
        {
            while(i < j && arr[j] > temp) //从右往左扫描，找到比基准元素小的值为止
                j--;

            if(i < j)
                arr[i++] = arr[j]; //交换二者的值 并i++ 向右移动一位

            while(i < j && arr[i] <= temp) //从左往右扫描，找到比基准元素大的值为止
                i++;

            if(i < j)
                arr[j--] = arr[i]; //交换二者的值，并j--
        }
        arr[i] = temp;  //填充基准元素
        return i;       //返回基准元素所在位置
    }
}

以上几个方法的测试类

import divide.*;

/**
 * 用于测试各种算法例题的具体实现
 */
public class Test {

    public static void main(String[] args) {
        TestQuickSort();
        //TestBinarysearch();
        //TestIntegerdivision();
        //TestFullPermutation();
        //TestMergesort();

    }
    public static void TestQuickSort(){
        QuickSort quickSort = new QuickSort();
        int[] a = {4,7,2,9,17,23,8,1,3};
        quickSort.quickSort(a,0,a.length-1);
        for(int i = 0;i < a.length; i++){
            System.out.print(a[i]+" ");
        }
    }

    public static void TestBinarysearch(){
        Binarysearch binarysearch = new Binarysearch();
        int[] a ={1,2,3,12,14,16,45,67,89};
       int result = binarysearch.search(a,16,0,a.length-1);
       System.out.println(result);
    }