一、歸并排序的遞歸探尋

1.思路

理想結果等于成分解斷開子結果表達式的公式表示

快速排序：

整個數(shù)組有序 = 其中一個元素有序 + 其左斷開數(shù)組有序 + 其右斷開數(shù)組有序

歸并排序：

整個數(shù)組有序 = 左斷開數(shù)組有序 + 右斷開數(shù)組有序 + 兩有序數(shù)組的有序合并

2.搭建

2.1設計過掉不符情況（在最底層時）

• if(array == null) return， 數(shù)組沒有元素不用排，下面是有元素
• if(left == right) return，只有一個元素已經(jīng)是有序了不用排，下面是多個元素
• if(left > right) return，排不了不要排的，之后下面是符合一般情況的多個元素 

2.2查驗能實現(xiàn)基礎排序（在最底層往上點時）

在最底層往上點時，有序數(shù)組有序合并操作在最底層能實現(xiàn)兩元素之間的比較然后進行排序的

2.3跳轉結果繼續(xù)往上回搭：

跳轉有序數(shù)組結果繼續(xù)往上有序合并維護回搭

3.實質

從底層的最小單個斷開有序數(shù)組往上有序地合并成越來越大的斷開有序數(shù)組直至合并完成一個整體的有序數(shù)組

4.實現(xiàn)

    public static void mergeSort(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }

    private static void mergeSortFunc(int[] array,int left,int right) {
        if(left >= right) return;
        int mid = (left+right) / 2;

        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }

    private static void merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid+1;
        int[] tmpArr = new int[right-left+1];
        int k = 0;
        //證明兩個區(qū)間 都同時有數(shù)據(jù)的
        while (s1 <= mid && s2 <= right) {
            if(array[s2] <= array[s1]) {
                tmpArr[k++] = array[s2++];
            }else {
                tmpArr[k++] = array[s1++];
            }
        }
        while (s1 <= mid) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= right) {
            tmpArr[k++] = array[s2++];
        }
        //tmpArr 里面一定是這個區(qū)間內有序的數(shù)據(jù)了
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+left] = tmpArr[i];
        }
    }

二、遞歸的調用棧

1.遞歸的執(zhí)行過程

在函數(shù)遞歸中，調用的函數(shù)里面執(zhí)行著再調用著隨著形參深入的不斷變化的函數(shù)自己：

第一次調用函數(shù)的執(zhí)行轉去等著第二次調用函數(shù)的執(zhí)行完，第二次調用函數(shù)的執(zhí)行也卡著轉去等第三次調用函數(shù)的執(zhí)行完，一層層形參變化著重復地執(zhí)行調用而都沒有往下去return，直到最后調用函數(shù)傳的形參變化到符合return的條件不再繼續(xù)往下調用了，return出結果開始往回地一層層促進上一層沒有執(zhí)行完到執(zhí)行完return，即開始往回地執(zhí)行往回地歸

2.遞歸的函數(shù)棧幀

所有任意一個函數(shù)的調用都會獨立開辟新的函數(shù)棧幀(里面存放局部變量、函數(shù)形參、返回地址、寄存器值）壓入調用棧中，在函數(shù)執(zhí)行到return語句結束后才彈出棧：

遞歸調用時，函數(shù)棧幀從先往后地一個個獨立地壓入棧中，往下遞歸直到形參條件變到return后由最新函數(shù)調用的棧幀開始往上彈棧幀出調用棧，在開始往上彈出棧幀開始有執(zhí)行完往回層往下執(zhí)行時，方法里面有可能寫的是繼續(xù)又去執(zhí)行調用當前層形參條件下的再來一波函數(shù)遞歸調用(形參變化可能就去設置成不同的了就會是左右不一樣的分支)，即是二叉即二叉樹的情況：

• 每一層不僅要左邊往下全執(zhí)行到底層然后開始往上全執(zhí)行到它那層的左邊結束，接著又要執(zhí)行右邊的往下執(zhí)行到底層然后再往上全執(zhí)行完到它的右層結束，最后它這個節(jié)點對應的這層函數(shù)才也執(zhí)行完它的棧幀也彈出調用棧，二叉樹從大到小所有的結構都是左邊往下全執(zhí)行完往上回來、右邊往下全執(zhí)行完往上回來、接著它這個節(jié)點的棧幀也往上彈返回執(zhí)行完 

2.1遞歸函數(shù)的棧幀壓彈

在歸并排序的二叉樹遞歸調用過程中：

• 每次累計著往下調用到底層時，此時的調用棧所占的空間是最大的、深度在二叉樹的最底層，調用棧的空間計算為調用棧里棧幀的個數(shù)×每個棧幀的內存大小，在每個函數(shù)的棧幀中，函數(shù)里面那些函數(shù)的調用信息、并非循環(huán)出現(xiàn)的常量個數(shù)的局部變量空間和都可算成常數(shù)的大小，所以在歸并排序這里，調用棧的最大空間為在調用棧里棧幀個數(shù)最多的時候：樹的高度log(n)*每個函數(shù)棧幀的內存大小是常數(shù)，即log(n)*常數(shù)，函數(shù)調用執(zhí)行完最底層后就開始有往上返回了，往上彈出最新最頂?shù)臈?/strong>
• 然后執(zhí)行完返回到上層時又回到當前層條件下的且新的形參變化模式的再往下遞歸，又會去壓棧到最底層，此時調用棧的空間又達到最大的log(n)
• 當它右邊往下的也全執(zhí)行完又往上返回到當前層時，就開始繼續(xù)往下接著執(zhí)行就開始有去調用合并有序數(shù)組的函數(shù)了