一、歸并排序的遞歸探尋

1.思路

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

快速排序：

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

歸并排序：

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

2.搭建

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

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

2.2查驗(yàn)?zāi)軐?shí)現(xiàn)基礎(chǔ)排序（在最底層往上點(diǎn)時(shí)）

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

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

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

3.實(shí)質(zhì)

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

4.實(shí)現(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;
        //證明兩個(gè)區(qū)間 都同時(shí)有數(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 里面一定是這個(gè)區(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é)果開始往回地一層層促進(jìn)上一層沒有執(zhí)行完到執(zhí)行完return，即開始往回地執(zhí)行往回地歸

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

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

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

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

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

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

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

執(zhí)行調(diào)用合并有序數(shù)列的函數(shù)時(shí)，調(diào)用棧又會壓入合并有序數(shù)組函數(shù)的棧幀，里面存放有開辟的當(dāng)前層數(shù)組元素個(gè)數(shù)大小的數(shù)組(非常量級的，要算的)，此時(shí)總的占用空間為調(diào)用棧的空間log(n-...)+n(-...)，因?yàn)?strong>合并有序數(shù)組函數(shù)的棧幀每次都是處在棧頂壓入的且函數(shù)里面并沒有再調(diào)用函數(shù)的在它之上再壓棧，所以它每次在棧頂進(jìn)來壓棧完就緊接著彈出棧的

三、歸并排序的復(fù)雜度

1.空間復(fù)雜度

空間復(fù)雜度計(jì)算的是整個(gè)執(zhí)行所有時(shí)刻中出現(xiàn)的最大瞬時(shí)占用空間：

從下層往上層的返回的過程中，遞歸函數(shù)的調(diào)用?？臻g變小著、合并有序數(shù)組的函數(shù)棧幀在變大著(里面的數(shù)組越來越大的)：

• 在最底層時(shí)占用的空間為遞歸函數(shù)的調(diào)用?？臻glog(n)+合并有序數(shù)組的函數(shù)棧幀0，即log(n)+0=log(n)
• 當(dāng)?shù)竭_(dá)最上層第一層時(shí)，遞歸函數(shù)的調(diào)用?？臻g是1，而合并有序數(shù)組的函數(shù)棧幀空間是n，此時(shí)的總空間大小是n，相比于最底層的log(n)及從下往上的過程中l(wèi)og(n)的遞減、n的遞增的總空間，此時(shí)的n是整個(gè)執(zhí)行所有時(shí)刻中出現(xiàn)的最大瞬時(shí)占用的空間，所以歸并排序的空間復(fù)雜度是O(n)

2.時(shí)間復(fù)雜度

時(shí)間復(fù)雜度即算整個(gè)遞歸調(diào)用執(zhí)行過程的時(shí)間和，我們可以不用按著遞歸搜索的過程去時(shí)時(shí)累計(jì)總的算，直接站在總二叉樹的角度一層一層地算所有時(shí)間的和就行了，一層層里面每一個(gè)樹節(jié)點(diǎn)及下的全執(zhí)行完對應(yīng)著該調(diào)用函數(shù)的全執(zhí)行完，因?yàn)檫f歸調(diào)用語句mergeSortFunc(array,left,mid)都是且已轉(zhuǎn)成里面的函數(shù)節(jié)點(diǎn)內(nèi)容來算了(調(diào)用中的去執(zhí)行調(diào)用部分是常量級的已不算)，且if(left >= right) return、int mid = (left+right) / 2也都是常量級的執(zhí)行時(shí)間不算，對應(yīng)到總的時(shí)間就是計(jì)算所有函數(shù)節(jié)點(diǎn)里的merge(array,left,right,mid)合并有序數(shù)組的時(shí)間和，每一層所有函數(shù)節(jié)點(diǎn)的合并有序數(shù)組時(shí)間和都為n(除了最后一層的函數(shù)節(jié)點(diǎn)進(jìn)去就直接判斷為return沒執(zhí)行有序數(shù)組合并)，一共有l(wèi)og(n)層，所以時(shí)間復(fù)雜度為O(n*log(n)) 

總結(jié)

到此這篇關(guān)于Java算法之歸并排序的文章就介紹到這了,更多相關(guān)Java算法歸并排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論