歸并排序
歸并排序（英語(yǔ)：merge sort）是一種采用了分治思想的排序算法。
所謂分治，即為分而治之。首先把一個(gè)序列分成兩部分，然后對(duì)這兩部分序列分別進(jìn)行排序。
那末如何對(duì)這兩部分序列進(jìn)行排序呢？請(qǐng)重新閱讀上面這句話。
說(shuō)白了，我們遞歸的把一個(gè)數(shù)列進(jìn)行分解，直到分割出的最小單元元素?cái)?shù)量<=2時(shí)。舉個(gè)例子，有一個(gè)11個(gè)元素的數(shù)列。
11 = 5+6 = 2 + 3 + 3 + 3 = 2 + 2 +1 +2 + 1 + 2 + 1
接下來(lái)模仿上面分解的過(guò)程進(jìn)行合并，在合并的過(guò)程中完成排序。這樣，排序好2個(gè)和1個(gè)元素的單元，然后把合并成3個(gè)和4個(gè)元素的單元，這時(shí)這樣的單元已經(jīng)部分有序，接下來(lái)繼續(xù)排序3個(gè)和4個(gè)元素的單元，然后再合并成……以此類推，直到合并成一個(gè)長(zhǎng)度為n的單元。
這樣我們可以得到歸并排序的工作過(guò)程：
三個(gè)步驟：
將數(shù)列劃分為兩部分；
遞歸地分別對(duì)兩個(gè)子序列進(jìn)行歸并排序；
合并兩個(gè)子序列。
不難發(fā)現(xiàn)，歸并排序的前兩步都很好實(shí)現(xiàn)，關(guān)鍵是如何合并兩個(gè)子序列。注意到兩個(gè)子序列在第二步中已經(jīng)保證了都是有序的了，第三步中實(shí)際上是想要把兩個(gè)?有序?的序列合并起來(lái)。
歸并排序的性質(zhì)：
歸并排序是一種穩(wěn)定的排序算法。
歸并排序的最優(yōu)時(shí)間復(fù)雜度、平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度均為O(n log n)?。
歸并排序的空間復(fù)雜度為 O(n)
C++代碼實(shí)現(xiàn)↓
鏈接：https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015?fr=aladdin
鏈接：https://oi-wiki.org/basic/merge-sort/
#include?<stdlib.h>#include?<stdio.h>void?Merge(int?sourceArr[],int?tempArr[],?int?startIndex,?int?midIndex,?int?endIndex){????int?i?=?startIndex,?j=midIndex+1,?k?=?startIndex;????while(i!=midIndex+1?&&?j!=endIndex+1)????{????????if(sourceArr[i]?>?sourceArr[j])????????????tempArr[k++]?=?sourceArr[j++];????????else????????????tempArr[k++]?=?sourceArr[i++];????}????while(i?!=?midIndex+1)????????tempArr[k++]?=?sourceArr[i++];????while(j?!=?endIndex+1)????????tempArr[k++]?=?sourceArr[j++];????for(i=startIndex;?i<=endIndex;?i++)????????sourceArr[i]?=?tempArr[i];}//內(nèi)部使用遞歸void?MergeSort(int?sourceArr[],?int?tempArr[],?int?startIndex,?int?endIndex){????int?midIndex;????if(startIndex?<?endIndex)????{????????midIndex?=?startIndex?+?(endIndex-startIndex)?/?2;//避免溢出int????????MergeSort(sourceArr,?tempArr,?startIndex,?midIndex);????????MergeSort(sourceArr,?tempArr,?midIndex+1,?endIndex);????????Merge(sourceArr,?tempArr,?startIndex,?midIndex,?endIndex);????}}int?main(int?argc,?char?*?argv[]){????int?a[8]?=?{50,?10,?20,?30,?70,?40,?80,?60};????int?i,?b[8];????MergeSort(a,?b,?0,?7);????for(i=0;?i<8;?i++)????????printf("%d?",?a[i]);????printf("\n");????return?0;}推薦例題：
洛谷P1309，P1908，P1774等
