前面介紹了冒泡沪饺、插入、選擇排序闷愤，下面我們介紹一個個人認(rèn)為稍微復(fù)雜點的排序整葡，歸并排序，首先看下歸并排序的思路肝谭。首先我們先思考一個問題掘宪，對于兩個有序的數(shù)組left與right，我們怎么給他們排序攘烛？是不是很簡單魏滚？一個for循環(huán)對left[i]和right[j]進(jìn)行比較，如果left[i]< right[j],將left[i]插入到新的數(shù)組中然后i++坟漱；反之將right[j]插入到數(shù)組中鼠次，然后j++。最后將left或者right數(shù)組中剩余的數(shù)列拼接到數(shù)組后面芋齿，就組成了一個有序的新數(shù)組腥寇。
代碼如下：
說到這里大家都理解吧？如果不理解自己在會從頭考慮下觅捆，我認(rèn)為這是理解歸并排序的第一步赦役，看明白了之后我們在往下看。
那么對于一個無序的數(shù)列栅炒，怎么將其變成兩個有序的數(shù)列掂摔，這就是歸并的核心，一旦變成了兩個有序的數(shù)列赢赊，然后用上面的merge函數(shù)乙漓，就可以完成這個數(shù)列的排序了。
試想首先將一個無序的數(shù)列兩個無序的數(shù)列释移，大家習(xí)慣的思路是采用折半叭披，前一半在前面，后一半在后面玩讳，將這兩個無序數(shù)列分別排序涩蜘，就可以構(gòu)成兩個有序的數(shù)列，但是細(xì)想下熏纯，對于每一半的無序數(shù)列又采取什么排序算法那皱坛？冒泡？插入還是選擇豆巨？他的時間復(fù)雜度都是O(n^2),這樣一來不僅僅沒有降低算法的時間復(fù)雜度剩辟，同時增加了代碼的復(fù)雜度。再順著這個思路思考下，將上面兩個無序的數(shù)列繼續(xù)折半下去贩猎，最終變成兩個單元數(shù)數(shù)列熊户，這樣就可以將其看成兩個有序的數(shù)列，然后用上面的merge函數(shù)進(jìn)行合并吭服，這樣就形成了一個有序的數(shù)列嚷堡，然后再將后面的兩個單元數(shù)數(shù)列進(jìn)行重復(fù)的操作，這樣就形成了多個2個元素的有序數(shù)列艇棕，依次類推蝌戒，多個4個元素的有序數(shù)列，最終形成多個元素的有序數(shù)列沼琉。說到這里不知道大家理解了嗎北苟？盜個圖放在這里看看：
對應(yīng)代碼如下：
至此，歸并排序完成打瘪。
