2020-1024=996：歸并排序！

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?
using?namespace?std;
const?int?N?=?1e5?+?10;
int?n;
int?q[N],?tmp[N];

void?merge_sort(int?q[],int?l,?int?r)
{
?if(l>=r)return;//判斷序列中是否為空或者只有一個(gè)數(shù)字，如果是的話，我們就不用排序了
?//確定分界點(diǎn)
?int?mid?=?l?+?r?>>?1;
?//遞歸處理
?merge_sort(q,l,mid);
?merge_sort(q,mid+1,r);
?//定義雙指針
?int?k?=0,i?=?l,?j=?mid+1;
?//歸并處理
?while(i?<=?mid?&&?j?<=?r)
??if(q[i]??else
??tmp[k++]?=?q[j++];
?//把源數(shù)組中剩余的數(shù)字（注意這里的數(shù)字一定是最小的)放到臨時(shí)數(shù)組后面去
?while(i?<=?mid)tmp[k++]?=?q[i++];
?while(j?<=?r)tmp[k++]?=?q[j++];
?//把臨時(shí)數(shù)組中排好序的數(shù)字放到源數(shù)組中去
?for(i?=?l,?j?=0;i<=r;i++,j++)q[i]=tmp[j];
}


int?main()
{
?scanf("%d",&n);
?for(int?i?=?0;i?{
??scanf("%d",&q[i]);
?}
?merge_sort(q,0,n-1);
?for(int?i?=?0;?i?{
??printf("%d?",q[i]);
?}
?return?0;
?
?
}

結(jié)果：

最后來(lái)一個(gè)更加生動(dòng)形象的歸并排序演示視頻(來(lái)源：https://visualgo.net/en/sorting)：