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

一、歸并排序：

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

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

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

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

2、舉例：

比如上圖我們有兩組已經(jīng)排好的序列數(shù)字，我們要進(jìn)行第三步合并，該如何進(jìn)行呢?思路如下：

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

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

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

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

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

3、歸并排序的平均時間復(fù)雜度的計算推導(dǎo):

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

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

二、代碼示例：

代碼：

#include usingnamespacestd; constintN=1e5+10; intn; intq[N],tmp[N]; voidmerge_sort(intq[],intl,intr) { if(l>=r)return;//判斷序列中是否為空或者只有一個數(shù)字，如果是的話，我們就不用排序了 //確定分界點 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]?

結(jié)果：

責(zé)任編輯：lq