歸併排序

介紹

歸併排序和快速排序一樣，都是基於分治思想的應用。
通過遞歸，不斷將原數列分為兩個數列，然後再分別使其有序，最後通過歸併將兩個有序子數列合併為新的有序數列。
值得註意的是，與快速排序不同，歸併排序是穩定的。

代碼實現

void merge_sort(int a[], int l, int r)
{
        if (l >= r) return;//判斷區間數據個數，為1則返回
        int  tmp[100001];//創建臨時數組
        int mid = l + r >> 1;
    	merge_sort(a, l, mid);
    	merge_sort(a, mid + 1, r);
    	int k = 0, i = l, j = mid + 1;//建立雙指針
    	while (i <= mid && j <= r)//其中一指針遍歷至結尾則終止
                if (a[i] <= a[j]) tmp[k++] = a[i++];//對比數據，誰小先加誰
                else tmp[k++] = a[j++];
    	while(i<=mid) tmp[k++] = a[i++];
    	while(j<=r) tmp[k++] = a[j++];//將剩餘數據依次放入
    	for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];//將排好的數據放回原數組
}

思路分析

void merge_sort(int a[], int l, int r)
{
        if (l >= r) return;//判斷區間數據個數，為1則返回
        int  tmp[100001];//創建臨時數組
        int mid = l + r >> 1;
    	merge_sort(a, l, mid);
    	merge_sort(a, mid + 1, r);

和快速排序先排序後遞歸不同，歸併排序是先遞歸，無限細分，重點在於回溯時的歸併，當遞歸到數組區間內只有1個數據時，肯定是有序的，經過歸併後返回的數組肯定也是有序的，所以我們這裡假設這個函數已經能夠實現目的，將一個數組分為兩部分然後分別排序，只需要用標記區間的起始位置和結束位置，而兩個區間的分界就是mid，而歸併的時候我們需要一個臨時存放數據的臨時數組tmp[]。

int k = 0, i = l, j = mid + 1;//建立雙指針
while (i <= mid && j <= r)//其中一指針遍歷至結尾則終止
        if (a[i] <= a[j]) tmp[k++] = a[i++];//對比數據，誰小先加誰
        else tmp[k++] = a[j++];

這裡便是整個演算法最關鍵的地方：數組的歸併。

首先，我們知道，兩個區間已經分別有序，而第一個區間起點便是本次函數傳入的起點l，終點為中值mid，第二個區間起點為mid+1，終點為函數傳入的終點參數r。

我們創建雙指針li和j，初始位置分別指向兩個取件的起始位置，不斷互相比較，值更小的放入數組然後往後遍歷，這樣就能實現整個數組的歸併，值得註意的是，我們的判斷條件為if(a[i]<=a[j])，這樣，就能保證同樣大小的數據按照原先的順序依次進入臨時數組，實現歸併排序的穩定性。

最終，當其中一個指針遍歷到區間結尾時，結束迴圈。

while(i<=mid) tmp[k++] = a[i++];
while(j<=r) tmp[k++] = a[j++];//將剩餘數據依次放入
for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];//將排好的數據放回原數組

當然，我們還需要將另外一個區間剩下的數據依次擠入臨時數組，實現最終的排序，那我們就通過比較指針和終點的值來實現。

最後將排好的數據從臨時數組中依次賦給原數組。

至此，我們完成了整個歸併排序演算法的閉環，完成了功能的實現。

結尾

歸併排序和快速排序都是分治思想的體現，他們的思路不僅僅能拿來排序，也能解決一些具體問題，具體選擇哪一種演算法，就要依靠你細緻入微的觀察，結合題目的特性。

最後，歸併排序和快速排序的時間複雜度一樣，都是O(nlogn)。

以上便是對歸併排序的介紹，本文由涼茶coltea撰寫，思路來自AcWing，大佬yxc的課程。