2020-1024=996：歸并排序！

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

一、歸并排序：

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

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

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

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

2、舉例：

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

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

b、然后指針i往下移動，如下圖所示,再次進行比較，明顯發(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、歸并排序的平均時間復雜度的計算推導:

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

從圖片的縱性來分析，當拆解到1的時候，這個時候什么數(shù)等于n除于它等于1，通過計算，我們知道是logn，然后再從橫向分析，我們要最多比較n個數(shù)字，所以歸并排序的時間復雜度就是：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;//判斷序列中是否為空或者只有一個數(shù)字，如果是的話，我們就不用排序了
?//確定分界點
?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ù)組后面去
?while(i?<=?mid)tmp[k++]?=?q[i++];
?while(j?<=?r)tmp[k++]?=?q[j++];
?//把臨時數(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;
?
?
}

結果：

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

參考：https://www.acwing.com/problem/content/description/789/