歸并排序詳解（后序遍歷）

大家可能都對(duì)二叉樹(shù)的后序遍歷比較熟悉，實(shí)際上歸并排序本質(zhì)框架就是二叉樹(shù)的后序遍歷，根結(jié)點(diǎn)的遍歷只不過(guò)換成了治（Merge方法的調(diào)用），本文將結(jié)合動(dòng)圖+代碼的方式進(jìn)行最通俗的講解。

「基本思想」：利用歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問(wèn)題分(divide)成一些小的問(wèn)題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案修補(bǔ)在一起，即分而治之)。

分的過(guò)程

下面自制配了一張動(dòng)圖來(lái)更好理解分的過(guò)程，其實(shí)完全就是左右根的后序遍歷，根的遍歷就是治（Merge方法的調(diào)用），分的過(guò)程中暫不可考慮根結(jié)點(diǎn)的遍歷，動(dòng)圖中僅展示左邊的分的過(guò)程，以mid將其分組，遞歸的終止條件就是left==right，每組的right和left都不相同，左邊遞歸調(diào)用傳值left的值不變，right值為mid，右邊遞歸調(diào)用傳值left為mid+1，因?yàn)閙id是左邊的最后一個(gè)，所以要加1，右邊的值就是right。

代碼如下：

public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left != right) {//left和right的值會(huì)根據(jù)mid的值不斷變化
        int mid = (left + right) / 2;
        //向左遞歸進(jìn)行分解，動(dòng)圖分組中靠左的部分
        mergeSort(arr, left, mid, temp);
        //向右遞歸進(jìn)行分解  動(dòng)圖分組中靠右的部分
        mergeSort(arr, mid + 1, right, temp);
        //合并(相當(dāng)于根)下面動(dòng)圖中暫未表示合的思路
        merge(arr, left, mid, right, temp);
    }
}

如下圖：「加上右邊邏輯上大致呈現(xiàn)二叉樹(shù)狀」

治---合的過(guò)程

根據(jù)二叉樹(shù)后序遍歷的特點(diǎn)，以本題為例，很明顯根節(jié)點(diǎn)需要遍歷7次，順序如下圖所示：

合并的規(guī)則如下：

定義一個(gè)與原數(shù)組長(zhǎng)度相等的臨時(shí)空數(shù)組temp，初始索引t=0，之后每次合并（共7次）左結(jié)點(diǎn)的起始索引為left，末尾索引為mid，右節(jié)點(diǎn)的起始索引為mid+1，末尾索引為right，利用while循環(huán)將左結(jié)點(diǎn)的每一個(gè)值與右結(jié)點(diǎn)的每一個(gè)值做比較，判斷條件為（left <= mid && mid+1 <= right）,如果左結(jié)點(diǎn)的值小于右結(jié)點(diǎn)的值，則將左結(jié)點(diǎn)的值賦給temp[t]，之后t++，為保證不修改left的值所以將值賦給變量i，i++；相反如果右節(jié)點(diǎn)的值小于左結(jié)點(diǎn)的值，右結(jié)點(diǎn)的值賦給temp[t]，之后t++，為保證不修改mid+1的值所以將值賦給變量j，j++；這步做完后，發(fā)現(xiàn)左右個(gè)結(jié)點(diǎn)一定會(huì)有值剩下，因?yàn)樽笥医Y(jié)點(diǎn)的值總會(huì)有一個(gè)先到達(dá)判斷條件，++之后就終止了while循環(huán)，因此會(huì)剩余，這時(shí)又會(huì)出現(xiàn)兩種情況，一是左邊剩余（可能不止一個(gè)），另一個(gè)是右邊剩余（可能不止一個(gè)），因此還需要while循環(huán)，如果左邊剩余說(shuō)明還沒(méi)到達(dá)mid（結(jié)尾索引），判斷條件為（i <= mid）,剩余元素一定是有序的并且是較大值，因此只需添加到臨時(shí)數(shù)組temp的末尾即可，右結(jié)點(diǎn)有值剩余只不過(guò)判斷條件變?yōu)椋╦ <= right），方法一樣。

最后每次合并都將temp的值copy到傳入的數(shù)組中去即可！

 public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左邊有序序列的初始索引
        int j = mid + 1;//右邊有序序列的初始索引
        int t = 0; //指向temp數(shù)組的當(dāng)前索引

        //一
        //先把左右兩邊有序的數(shù)據(jù)按照規(guī)則填充到temp數(shù)組
        //直到左右兩邊的有序序列，有一邊處理完畢為止
        while (i <= mid && j <= right) { //繼續(xù)
            //如果左邊的有序序列的當(dāng)前元素小于等于右邊有序序列的當(dāng)前元素
            //即將左邊的當(dāng)前元素填充到temp數(shù)組
            //然后t++，i++
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else { //反之，則將右邊的有序序列當(dāng)前元素填充到temp數(shù)組
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        while (i <= mid) {//將左邊剩余元素全部填充進(jìn)temp中
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {//將右序列剩余元素全部填充進(jìn)temp中
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        //三
        //將temp數(shù)組的元素拷貝到arr
        //注意，并不是每次都拷貝所有
        t = 0;
        int tempLeft = left;
        //第一次合并tempLeft=0，right=1  tempLeft=2，right=3  tempLeft=0，right=3
        //最后一次tempLeft=0，right=1
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }

「由于合并次數(shù)過(guò)多，下圖僅將最后一次合并圖解在下圖」：

「第七次合并動(dòng)圖圖解：」

第七次合并是最后一次合并，可以看到數(shù)組已經(jīng)有序了，最后將temp數(shù)組copy到原數(shù)組即可排序完成！

時(shí)間復(fù)雜度：O(nlogn)

空間復(fù)雜度：O(n+logn)

由于歸并排序在歸并過(guò)程中需要與原始記錄序列同樣數(shù)量的存儲(chǔ)空間存放歸并結(jié)果以及遞歸深度為log2n的?？臻g，因此空間復(fù)雜度為O(n+logn)，會(huì)造成空間的浪費(fèi)，因此可采用迭代繼續(xù)優(yōu)化，但是思路比較復(fù)雜，在本篇文章不做講解！