演算法工程師的升級之路-數據結構與演算法篇(2)歸併排序

引言

　　本次將要介紹歸併排序演算法，歸併排序是分治演算法的一個很典型的例子，將排序問題遞歸地拆分為子數組的排序問題(分)，然後逐個攻破，通過歸併操作將排序好的數組進行合併。

歸併操作

　　歸併操作是歸併演算法的核心步驟，歸併演算法的輸入是兩個排序好的子數組，返回一個合併的排序好的數組。

　　為了方便實現，以下歸併操作是藉助輔助數組的C++實現

void merge(std::vector<int> &a, int lo, int mid, int hi)
{//合併兩個有序子數組為一個有序數組a[lo, ..., mid]+a[mid+1, ..., hi] ---> a[lo, ..., hi]
    int i=lo,j=mid+1;                               //兩個子數組的指針
    std::vector<int> aux(a.size(),0);               //輔助數組
    for(int k=lo;k<=hi;k++) aux[k]=a[k];
    for(int k=lo;k<=hi;k++)
    {
        if(i>mid)               a[k]=aux[j++];      //第一個數組的索引有效範圍是i：[lo, ..., mid], 當i>mid說明第一個子數組的元素已經被取完了，故取第二個子數組的元素
        else if(j>hi)           a[k]=aux[i++];      //同理，第二個數組元素被取完
        else if(aux[j]<aux[i])  a[k]=aux[j++];      //兩個數組都沒被取完，則將比較小的元素放到合併後的數組前面
        else                    a[k]=aux[i++];      //邏輯同上
    }
}

　下面結合影像來理解歸併操作的原理。上面兩個分離的子數組為aux，為了方便區分，沒有將它們畫到一個數組裡，實際上這兩個子數組是通過索引的範圍來確定的；下面的數組為a。藍色代表已經放置在正確位置上的元素。

　　此處第二個子數組的元素被取完，所以直接將第一個子數組的元素放置到數組a的對應位置即可。

遞歸排序

　　歸併操作十分地簡單且直接，真正讓歸併排序發揮出威力的是分的操作。此處藉助遞歸和歸併操作，實現自頂向下的歸併排序。

void merge_sort(std::vector<int> &a, int lo, int hi)
{//使用歸併排序對數組a[lo, ..., hi]進行排序
    if(lo>=hi) return;              //數組不多於1個元素，已經有序
    int mid = lo+(hi-lo)/2;         //這裡是為了避免相加結果溢出
    merge_sort(a, lo, mid);         //對切分的子數組排序
    merge_sort(a, mid+1, hi);
    merge(a, lo, mid, hi);          //對切分後有序的兩個子數組進行合併操作
}

　　下面為了理解歸併排序，繪製函數的遞歸調用樹。

　　從程式碼實現來看，可以發現這種遞歸形式與二叉樹的後續遍歷是一樣的形式，下面以長度為4的數組為例

merge_sort(a,0,3)
    merge_sort(a,0,1)
    |   merge_sort(a,0,0)
    |   merge_sort(a,1,1)
    |   merge(a,0,0,1)
    merge_sort(a,2,3)
    |   merge_sort(a,2,2)
    |   merge_sort(a,3,3)
    |   merge(a,2,2,3)
    merge(a,0,1,3)

時空複雜度分析

　　首先進行簡單的分析，經過上面的分析，以長度為8的數組為例，函數調用的遞歸樹如下圖

　　可以發現歸併函數的遞歸樹為滿二叉樹，結點的每一次分裂都是數組長度減半，所以遞歸樹高度為log n。每一次分割對應一次歸併操作，歸併操作的時間複雜度為O(n)。所以對於歸併排序演算法的時間複雜度為O(n logn)。

　　通過列歸併排序演算法的時間複雜度遞推關係式，又遞歸程式碼可知，歸併排序將數組排序分解為大小減半的兩個子數組的歸併排序和一個歸併操作，其中歸併操作的時間複雜度為線性時間複雜度，得到T(n)=2T(n/2)+O(n)。

　　根據主定理，當T(n)=aT(n/b)+f(n)，f(n)=O(n^d)時

　　①T(n)=O(n^d)，當a<b^d時

　　②T(n)=O(n^dlog n)，當a=b^d時

　　③T(n)=O(n^log_ba)，當a>b^d時

　　由已知條件，屬於情況②，所以得到時間複雜度為O(n logn)。

　　對於空間複雜度，藉助輔助數組的歸併排序演算法是線性空間複雜度的O(n)。同時還有inplace版本的歸併排序演算法實現，所以空間複雜度為O(1)，有興趣的同學可以自己去看看。

總結

　　本次我們學習了歸併排序的基本思想和簡單自頂向下的的演算法程式碼實現，歸併排序演算法是一個很經典的分治演算法的例子，將問題進行分解的思路在日常生活中也是很實用的思想。推薦大家在學習時結合影像進行思考，充分調動左右腦，這裡是一個關於歸併演算法的一個可視化(//www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)

Tags: 演算法工程師的升級之路