一、歸并排序的遞歸探尋

1.思路

理想結(jié)果等于成分解斷開子結(jié)果表達(dá)式的公式表示

快速排序：

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

歸并排序：

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

2.搭建

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

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

2.2查驗?zāi)軐崿F(xiàn)基礎(chǔ)排序（在最底層往上點時）

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

2.3跳轉(zhuǎn)結(jié)果繼續(xù)往上回搭：

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

3.實質(zhì)

從底層的最小單個斷開有序數(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ū)間內(nèi)有序的數(shù)據(jù)了
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+left] = tmpArr[i];
        }
    }

二、遞歸的調(diào)用棧

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

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

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

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

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

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

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

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

在歸并排序的二叉樹遞歸調(diào)用過程中：

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