今天繼續給大家分享排序算法里面的另外一種排序算法：歸并排序!

一、歸并排序：

1、歸并排序操作的核心思想：

a、確定分界點:mid=(l+r)/2

b、遞歸排序左邊和右邊(排完左右兩邊的數，就會成為兩個有序的序列了)

c、歸并（把上面的兩個有序序列合并成一個有序的序列，用一個簡單的詞來說，就是合二為一！）

2、舉例：

比如上圖我們有兩組已經排好的序列數字，我們要進行第三步合并，該如何進行呢?思路如下：

a、這里先定義一個空的數組res，它主要是為了臨時存放合并序列排序好的數字；我們從圖中可以看到，第一個序列指針i指向數字1，第二序列指針j指向2，這個時候我們要比較兩個數字的大小,小的數字就放到臨時數組res里面去，這里我們明顯知道數字1小于2，所以把1放到臨時數組res里去

b、然后指針i往下移動，如下圖所示,再次進行比較，明顯發現指針j指向的數字2更小，把它放到res里面去，然后指針j往下移動，指針i不動，后面依次類推

c、如下圖所示，兩個指針都指向了數字5，如果遇到兩個數字一樣的話，一般是把第一個序列的數字放到臨時數組res里面去，這點稍微要注意一下

d、最后把臨時數組里面的是數字放到原來的數組里面去

注意：一個算法穩定，并不能說它的時間效率是穩定的；這里的穩定是說兩個序列中有兩個數是相同的，如果在排完序之后，他們的位置還是沒有發生變化的話，那么這個排序就是穩定的，反之亦然!

3、歸并排序的平均時間復雜度的計算推導:

注：圖片來源：https://visualgo.net/zh/sorting

從圖片的縱性來分析，當拆解到1的時候，這個時候什么數等于n除于它等于1，通過計算，我們知道是logn，然后再從橫向分析，我們要最多比較n個數字，所以歸并排序的時間復雜度就是：nlogn

二、代碼示例：

代碼：

#include usingnamespacestd; constintN=1e5+10; intn; intq[N],tmp[N]; voidmerge_sort(intq[],intl,intr) { if(l>=r)return;//判斷序列中是否為空或者只有一個數字，如果是的話，我們就不用排序了 //確定分界點 intmid=l+r>>1; //遞歸處理 merge_sort(q,l,mid); merge_sort(q,mid+1,r); //定義雙指針 intk=0,i=l,j=mid+1; //歸并處理 while(i<=?mid?&&?j?<=?r) ??if(q[i]?

結果：

責任編輯：lq