五大常用算法

1，分治法

定义：把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
合并排序

image.png

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {85,3,52,9,7,1,5,4, 2};
        merge(arr);
    }

    /**
     *
     * @param arr
     */
    static void merge(int[] arr) {
        int length = arr.length;
        int mid = length / 2;
        if (mid == 0) {
            return;
        }
        int[] leftArr= Arrays.copyOfRange(arr,0,mid);//拷贝数组array的左半部分
        int[] rightArr=Arrays.copyOfRange(arr,mid,length);//拷贝数组array的右半部分
        System.out.println("-----------------------");
        System.out.println(JSON.toJSONString(leftArr));
        System.out.println(JSON.toJSONString(rightArr));
        // 递归至最小单位
        merge(leftArr); // 这里把arr变掉了！！找了半天
        merge(rightArr);
        sort(arr, leftArr, rightArr); // 这里的arr就是每个left,right,,,不要晕
        System.out.println("++++++++++++++++++++++");
        System.out.println(JSON.toJSONString(arr));
    }

    /**
     * 排序
     * @param result
     * @param left
     * @param right
     */
    static void sort(int[] result, int[] left, int[] right) {
        int i=0,l=0,r=0;
        while(l<left.length&&r<right.length){
            if(left[l]<right[r]){
                result[i]=left[l];
                i++;
                l++;
            }else{
                result[i]=right[r];
                i++;
                r++;
            }
        }
        while(r<right.length){//如果右边剩下合并右边的
            result[i]=right[r];
            r++;
            i++;
        }
        while(l<left.length){
            result[i]=left[l];
            l++;
            i++;
        }
    }
}

打印结果

-----------------------
[85,3,52,9]
[7,1,5,4,2]
-----------------------
[85,3]
[52,9]
-----------------------
[85]
[3]
++++++++++++++++++++++
[3,85]
-----------------------
[52]
[9]
++++++++++++++++++++++
[9,52]
++++++++++++++++++++++
[3,9,52,85]
-----------------------
[7,1]
[5,4,2]
-----------------------
[7]
[1]
++++++++++++++++++++++
[1,7]
-----------------------
[5]
[4,2]
-----------------------
[4]
[2]
++++++++++++++++++++++
[2,4]
++++++++++++++++++++++
[2,4,5]
++++++++++++++++++++++
[1,2,4,5,7]
++++++++++++++++++++++
[1,2,3,4,5,7,9,52,85]

快速排序

image.png

public class FastSort {
    public static int[] qsort(int arr[],int start,int end) {
        if (start > end) {
            return arr;
        }
        int i = start;
        int j = end;
        int temp = arr[start];
        while (i != j) {
            while (j > i && arr[j] >= temp) {
                j--; // 循环右边直到找到比temp小的值
            }
            while (j > i && arr[i] <= temp) {
                i++; // 循环左边直到找到比temp大的值
            }
            if (j > i) {
                int tem = arr[i]; // 将大值放右边，小值放左边
                arr[i] = arr[j];
                arr[j] = tem;
            }
        }
        // 这个时候i等于j，互换中间那个数字和temp的位置，因为中间那个值肯定是小于temp的，所以放左边
        arr[start] = arr[i];
        arr[i] = temp;
        qsort(arr, start, i - 1); // 递归处理左边的
        qsort(arr, i + 1, end); // 递归处理右边的
        return (arr);
    }
    public static void main(String[] args) {
        int arr[] = new int[]{5,3,2,9,8,10,7,6,1,4};
        int len = arr.length-1;
        arr=qsort(arr,0,len);
        for (int i:arr) {
            System.out.print(i+"\t");
        }
    }
}

2，贪心法

定义：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
适用：局部最优策略能导致产生全局最优解。

3，动态规划算法

定义：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。

4，回溯法

-定义：回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

5，分支限界法

-定义：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
-对比：分支限界法与回溯法的不同
（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。