1、递归算法

用递归算法求数组 arr[] 中的最大值 N
程序实现：

public class Code08_GetMax {
    public static void main(String[] arr){
        int[] arrs = {2,3,5,1,4,6};
        System.out.println(getMax(arrs));

    }

    public static int getMax(int[] arr){
        return process(arr, 0, arr.length -1);
    }
    //arr[L..R]范围上求最大值     N
    public static int process(int[] arr, int L, int R){
        if(L == R){ // arr[L..R]范围上只有一个数，直接返回
            return arr[L];
        }
        int mid = L + ((R - L) >> 1); // 中点
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1,R);
        return Math.max(leftMax, rightMax);
    }
}

递归逻辑图解如下图所示：

递归算法图解.png
master公式求解递归时间复杂度： master公式.png

---

2、归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
2）让其整体有序的过程里用了排外序方法
3）利用master公式来求解时间复杂度
4）归并排序的实质

时间复杂度O(N*logN)，额外空间复杂度O(N)

归并排序算法实现：java

import java.util.Arrays;

public class Code01_MergeSort {

    public static void main(String []args){ //主函数
        int []arr = {9,8,7,6,5,4,3,2,1};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void mergeSort(int[] arr){  //归并排序
        if (arr == null || arr.length < 2){
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R){  //分
        if(L == R){
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L,mid, R); //将两个有序子数组合并
    }

    public static void merge(int[] arr, int L, int M, int R){ //合并
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L; //左序列指针
        int p2 = M + 1; //右序列指针
        while(p1 <= M && p2 <= R){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++]:arr[p2++];
        }
        while(p1 <= M){ //将左边剩余元素填充进help中
            help[i++] = arr[p1++];
        }
        while(p2 <= R){ //将右序列剩余元素填充进help中
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++){ //将排好序的数组回写到原数组
            arr[L + i] = help[i];
        }
    }
}