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

一、歸并排序：

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

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

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

c、歸并（把上面的兩個(gè)有序序列合并成一個(gè)有序的序列，用一個(gè)簡(jiǎn)單的詞來(lái)說(shuō)，就是合二為一?。?/p>

2、舉例：

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

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

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

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

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

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

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

注：圖片來(lái)源：https://visualgo.net/zh/sorting

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

二、代碼示例：

代碼：

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