歸并排序（Merge Sort）是數(shù)組排序算法中一種常見的算法，其主要思想為經(jīng)典的“分治思想”。本文將介紹數(shù)組排序算法中的歸并排序，并介紹其相關(guān)應(yīng)用。??本文的文章結(jié)構(gòu)分布如下：

從合并兩個(gè)有序數(shù)組講起

(相關(guān)資料圖)

數(shù)組歸并排序

合并K個(gè)有序數(shù)組

歸并排序的應(yīng)用

首先，我們從合并兩個(gè)有序數(shù)組開始，這是歸并排序的基礎(chǔ)。

假設(shè)我們有兩個(gè)已經(jīng)排好序（不妨假設(shè)為升序）的數(shù)組nums1和nums2，如何將這兩個(gè)數(shù)組合并起來呢？其實(shí)想法是比較簡單的，就是用雙指針法。用兩個(gè)指針分別指向這兩個(gè)數(shù)組，然后分別從頭到尾遍歷，需要注意比較兩個(gè)指針指向的數(shù)字大小，具體算法如下：

假設(shè)合并后的數(shù)字為sorted，初始化為空數(shù)組；

如果指向數(shù)組nums1的指針已經(jīng)達(dá)到數(shù)組nums1的末尾，則將數(shù)組nums2中的剩余元素依次添加至sorted中；

如果指向數(shù)組nums2的指針已經(jīng)達(dá)到數(shù)組nums2的末尾，則將數(shù)組nums1中的剩余元素依次添加至sorted中；

如果兩個(gè)指針都沒有達(dá)到數(shù)組的結(jié)尾，則比較該指針指向的數(shù)字，數(shù)字小的添加至sorted中，同時(shí)該指針向后移動(dòng)一位。??我們以數(shù)組[1,2, 3]和[2,5,6]為例，其合并過程如下圖：

該算法的Python程序如下：

defmerge(nums1,nums2):result=[]m,n=len(nums1),len(nums2)p1,p2=0,0whilep1
運(yùn)行結(jié)果如下：
arrays:[1,2,3]and[2,5,6],merge:[1,2,2,3,5,6]arrays:[1,2]and[2,5,6],merge:[1,2,2,5,6]arrays:[1,2,3,4]and[2,5,6],merge:[1,2,2,3,4,5,6]
數(shù)組歸并排序 
經(jīng)過上述介紹，我們已經(jīng)知曉如何合并兩個(gè)有序數(shù)組了。接下來，我們討論如何對(duì)數(shù)組進(jìn)行排序。利用“分而治之”的想法，我們將原始數(shù)組result分為兩部分left和right，兩部分長度盡可能接近。如果left和right已經(jīng)排好序了，那么將這兩個(gè)排序數(shù)組合并即可。問題就變?yōu)槿绾螌eft和right排序？但此時(shí)，我們發(fā)現(xiàn)left和right的長度大約為原始元素result的一半，因此我們可以不停地left和right拆分，直到它們的長度為0或者1，那么此時(shí)這兩個(gè)數(shù)組已經(jīng)排好序了，最后我們?cè)賹⒎植鸷蟮臄?shù)組自下而上地進(jìn)行合并結(jié)果即可。??我們以數(shù)組[6,5,12,10,9,1]為例，具體演示該過程：
歸并排序的Python實(shí)現(xiàn)代碼如下（merge函數(shù)參考前面代碼）：
defmerge_sort(lst):iflen(lst)<=1:returnlst#從遞歸中返回長度為1的序列middle=len(lst)//2left=merge_sort(lst[:middle])#通過不斷遞歸，將原始序列拆分成n個(gè)小序列right=merge_sort(lst[middle:])returnmerge(left,right)if__name__=="__main__":a=[6,5,12,10,9,1]result=merge_sort(a)print("array:{},aftermergesort:{}".format(a,result))a=[6,5,12,10]result=merge_sort(a)print("array:{},aftermergesort:{}".format(a,result))a=[1,2,3,2,5,6]result=merge_sort(a)print("array:{},aftermergesort:{}".format(a,result))
運(yùn)行結(jié)果如下：
array:[6,5,12,10,9,1],aftermergesort:[1,5,6,9,10,12]array:[6,5,12,10],aftermergesort:[5,6,10,12]array:[1,2,3,2,5,6],aftermergesort:[1,2,2,3,5,6]
數(shù)組的歸并排序算法的時(shí)間復(fù)雜度為O(n*log n), 空間復(fù)雜度為O(n)，其中n代表數(shù)組的長度，并且歸并排序算法是穩(wěn)定的。
合并K個(gè)有序數(shù)組 
假如我們將合并兩個(gè)有序數(shù)組擴(kuò)展成K個(gè)有序數(shù)組（不妨假設(shè)都是升序排列）的情形呢？其實(shí)，我們也可以借鑒數(shù)組的歸并排序的思想。??我們將長度為K的有序數(shù)組列表，按中間數(shù)組分成長度大致相同的兩個(gè)數(shù)組列表，利用分拆、合并的辦法可以將這兩個(gè)數(shù)組列表合并（此時(shí)問題的數(shù)組列表規(guī)模大致為原先的一半），再合并生成的這兩個(gè)列表即可。??具體實(shí)現(xiàn)的Python代碼如下：
defmerge_k_sort(lists):n=len(lists)ifn==0:return[]elifn==1:returnlists[0]else:middle=n//2left=merge_k_sort(lists[:middle])right=merge_k_sort(lists[middle:])returnmerge(left,right)if__name__=="__main__":lists=[[1,2],[3,5],[7,9]]result=merge_k_sort(lists)print("lists:{},aftermerge:{}".format(lists,result))lists=[[1,2],[3,5],[7,9],[4,10]]result=merge_k_sort(lists)print("lists:{},aftermerge:{}".format(lists,result))lists=[[1,2],[3,5],[7,9],[4,10],[6,8,12]]result=merge_k_sort(lists)print("lists:{},aftermerge:{}".format(lists,result))
運(yùn)行結(jié)果如下：
lists:[[1,2],[3,5],[7,9]],aftermerge:[1,2,3,5,7,9]lists:[[1,2],[3,5],[7,9],[4,10]],aftermerge:[1,2,3,4,5,7,9,10]lists:[[1,2],[3,5],[7,9],[4,10],[6,8,12]],aftermerge:[1,2,3,4,5,6,7,8,9,10,12]
其實(shí)，我們可以將數(shù)組的排序轉(zhuǎn)化為合并K個(gè)數(shù)組問題。我們只需要將數(shù)組的每個(gè)元素單獨(dú)組成一個(gè)列表，長度為1，則合并這些長度為1的列表即可，因?yàn)樗鼈円呀?jīng)排好序了！
if__name__=="__main__":nums=[6,5,12,10,9,1]lists=[[x]forxinnums]result=merge_k_sort(lists)print("array:{},result:{}".format(nums,result))
歸并排序的應(yīng)用 
該部分將介紹歸并排序的應(yīng)用，主要介紹數(shù)組的逆序?qū)栴}。歸并排序的應(yīng)用主要如下：
鏈表排序
數(shù)組的逆序?qū)?shù)量問題
外部排序（External Sorting）
其中鏈表排序也可以用歸并排序思想實(shí)現(xiàn)，其大致思路差不多，主要是鏈表本身與數(shù)組的數(shù)據(jù)結(jié)構(gòu)上的差異，其基礎(chǔ)仍然是合并兩個(gè)有序鏈表。??重點(diǎn)介紹數(shù)組的逆序?qū)?shù)量問題。所謂數(shù)組的逆序?qū)?，指的是?duì)于數(shù)組a的兩個(gè)下標(biāo)位置i和j，滿足ia[j]。用數(shù)組的逆序?qū)?shù)量可以衡量這個(gè)數(shù)組的排序情況，如果數(shù)組是升序排序，則逆序?qū)?shù)量為0；如果數(shù)組是逆序排序，則逆序?qū)?shù)量最大。比如：
數(shù)組[8,4,2,1]，其逆序?qū)?shù)量為6；
數(shù)組[1, 20, 6, 4, 5]，其逆序?qū)?shù)量為5；
我們也用歸并排序思想也解決數(shù)組的逆序?qū)?shù)量問題。我們考慮以下情況：
對(duì)于數(shù)組a，將其拆分成inv1和inv2，那么數(shù)組a的逆序?qū)?shù)量，應(yīng)該是inv1的逆序?qū)?shù)量加上inv2的逆序?qū)?shù)量以及inv1和inv2按升序排列后合并時(shí)產(chǎn)生的逆序?qū)?shù)量。??將inv1和inv2升序排列，可以用歸并排序思想。那么為什么要對(duì)inv1和inv2按升序排列呢？這是因?yàn)?，如果將inv1和inv2升序排序后，如果inv1中的位置i和inv2中的位置j滿足inv1[i]>inv2[j],那么inv1在i后面的元素都大于inv2[j]，這樣就方便計(jì)算了。
數(shù)組的逆序?qū)?shù)量問題的Python實(shí)現(xiàn)代碼如下：
#FunctiontoUseInversionCountdefmergeSort(arr,n):temp_arr=[0]*nreturn_mergeSort(arr,temp_arr,0,n-1)#ThisFunctionwilluseMergeSorttocountinversionsdef_mergeSort(arr,temp_arr,left,right):inv_count=0ifleft
總結(jié) 
本文主要介紹了數(shù)組排序中的歸并排序思想及其在數(shù)組逆序?qū)χ械膽?yīng)用。??歡迎大家訪問我的CSDN博客：https://blog.csdn.net/jclian91，后續(xù)我的文章將全部在上面展示，個(gè)人的微信公眾號(hào)將另作他用，屆時(shí)將不會(huì)在該公眾號(hào)上發(fā)布技術(shù)文章。
參考網(wǎng)址： 
合并兩個(gè)有序數(shù)組: https://leetcode.cn/problems/merge-sorted-array/description/
劍指 Offer 51. 數(shù)組中的逆序?qū)? https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
Merge Sort Algorithm: https://www.geeksforgeeks.org/merge-sort/
Inversion count in Array using Merge Sort: https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/
Merge Sort Algorithm: https://www.programiz.com/dsa/merge-sort
 

關(guān)鍵詞：         
       歸并排序 
              
       數(shù)組排序