演算法淺談——歸併演算法求解逆序數
- 2020 年 3 月 5 日
- 筆記
點擊上方藍字，和我一起學技術。
在之前介紹線性代數行列式計算公式的時候，我們曾經介紹過逆序數：我們在列舉出行列式的每一項之後，需要通過逆序數來確定這一項符號的正負性。如果有忘記的同學可以回到之前的文章當中複習一下：
如果忘記呢，問題也不大，這個概念比較簡單，我想大家很快就能都搞清楚。
今天的這一篇文章，我想和大家聊聊逆序數的演算法，也是一道非常經典的演算法題，經常在各大公司的面試題當中出現。
我們先來回顧一下逆序數的定義，所謂逆序數指的是數組當中究竟存在多少組數對，使得排在前面的數大於排在後面的數。我們舉個例子，假設當下有一個數組是: [1, 3, 2]。
對於數對(3, 2)來說，由於3排在2前面，並且3 > 2，那麼就說明(3, 2)是一對逆序數對。整個數組當中所有逆序數對的個數就是逆序數。
我們從逆序數的定義當中不難發現，逆序數其實是用來衡量一個數組有序程度的一個指標。逆序數越大，說明這個數組遞增性越差。如果逆序數為0，說明這個序列是嚴格遞增的。如果一個長度為n的數組的逆序數是，那麼說明這個數組是嚴格遞減的，此時逆序數最大。
那麼，我們怎麼快速地求解逆序數呢？
暴力解法
顯然，這個問題可以暴力求解，我們只需要遍歷所有的數對，然後判斷是否構成逆序即可，最後累加一下所有逆序數對的個數就是最終的答案。
這個程式碼非常簡單，只需要幾行：
inverse = 0 for i in range(1, 10): for j in range(0, i): if arr[j] > arr[i]: inverse += 1
這樣當然是可以的，但是我們也很容易發現，這樣做的時間複雜度是，這在很多時候是我們不能接受的。即使是運行速度非常快的C++，在單核CPU上一秒鐘的時間，也就能跑最多n=1000這個規模。再大需要消耗的時間就會陡然增加，而在實際應用當中，一個長度超過1000的數組簡直是家常便飯。顯然，我們需要優化這個演算法，不能簡單地暴力求解。
分治
我們可以嘗試使用分治演算法來解決這個問題。
對於一個數組arr來說，我們試著將它拆分成兩半，比如當下arr是[32, 36, 3, 9, 29, 16, 35, 73, 34, 82]。我們拆分成兩半之後分別是[32, 36, 3, 9, 29]和[16, 35, 73, 34, 82]。
我們令左邊半邊的子數組是A，右邊半邊的子數組是B。顯然A和B都是原問題的子問題，我們可以假設通過遞歸可以求解出A和B子問題的結果。
那麼問題來了，我們怎麼通過A、B子問題的結果來構建arr的結果呢？也就是說，我們怎麼通過子問題分治來獲取原問題的答案呢？
在回答之前，我們先來分析一下當前的情況。當我們將arr數組拆分成了AB兩個部分之後，整個arr的逆序數就變成了三個部分。分別是A數組之間的逆序數、B數組之間的逆序數，以及AB兩個數組之間的逆序數，也就是一個元素在A中，一個元素在B中的逆序數對。
我們再來分析一下，會發現A數組中的元素交換位置，只會影響A數組之間的逆序數，並不會影響B以及AB之間構成的逆序數。因為A中的元素即使交換位置，也還是在B數組所有元素之前。
我們舉個例子：
假設arr=[3, 5, 1, 4]，那麼A=[3, 5], B=[1, 4]。對於arr而言，它的逆序數是3分別是(3， 1)， （5， 1）和（5， 4）。對於A而言，它的逆序數是0，B的逆序數也是0。我們試著交換一下B當中的位置，交換之後的B=（4， 1），此時arr=[3, 5, 4, 1]。那麼B的逆序數變成1，A的逆序數依然還是0。而整體arr的逆序數變成了4，分別是：（3， 1），（5， 1），（5， 4）和（4，1），很明顯整體的逆序數新增的就是B交換元素帶來的。通過觀察，我們也能發現，對於A中的3和5而言，B中的1和4的順序並不影響它們構成逆序數的數量。
想明白了這一層，剩下的就簡單了。既然A和B當中的元素無論怎麼交換順序也不會影響對方的結果，那麼我們就可以放心地使用分治演算法來解決了。我們先假設，我們可以通過遞歸獲取A和B各自的逆序數。那麼剩下的問題就是找出所有A和B個佔一個元素的逆序數對的情況了。
我們先對A和B中的元素進行排序，我們之前已經驗證過了，我們調整A或者B當中的元素順序，並不會改變橫跨AB逆序數的數量，而我們通過遞歸已經求到了A和B中各自逆序數對的數量，所以我們存下來之後，就可以對A和B中的元素進行排序了。A和B中元素有序了之後，我們可以用插入排序的方法，將A中的元素依次插入B當中。
B: XXXXXXXXX j XXXXXXXXXXXX / ai
從上圖我們可以看出來，假設我們把這個元素插入B數組當中j的位置。由於之前排在B這j個元素之前，所以構成了j個逆序數對。我們對於所有A中的元素求出它在B數組所有插入的位置j，然後對j求和即可。
比較容易想到，由於B元素有序，我們可以通過二分的方法來查找A當中元素的位置。但其實還有更好的辦法，我們一個步驟就可以完成AB的排序以及插入，就是將AB兩個有序的數組進行歸併。
在歸併的過程當中，我們既可以知道插入的B數組中的位置，又可以完成數組的排序，也就順帶解決了A和B排序的問題。所以整個步驟其實就是歸併排序的延伸，雖然整個程式碼和歸併排序差別非常小，但是，這個過程當中的推導和思考非常重要。
如果你能理解上面這些推導過程，我相信程式碼對你來說並不困難。如果你還沒能完全理解，也沒有關係，借著程式碼，我相信你會理解得更輕鬆。話不多說了，讓我們來看程式碼吧：
def inverse_num(array): n = len(array) if n <= 1: return 0, array mid = n // 2 # 將數組拆分為二往下遞歸 inverse_l, arr_l = inverse_num(array[:mid]) inverse_r, arr_r = inverse_num(array[mid:]) nl, nr = len(arr_l), len(arr_r) # 插入最大的int作為標兵，可以簡化判斷超界的程式碼 arr_l.append(sys.maxsize) arr_r.append(sys.maxsize) i, j = 0, 0 new_arr = [] # 存儲array對應的逆序數 inverse = inverse_l + inverse_r while i < nl or j < nr: if arr_l[i] <= arr_r[j]: # 插入A[i]的時候逆序數增加j，因為A[i]放在了B數組j個元素前面，構成了j個逆序數對 inverse += j new_arr.append(arr_l[i]) i += 1 else: new_arr.append(arr_r[j]) j += 1 return inverse, new_arr
從程式碼層面來看，上面這段程式碼實現了歸併排序的同時也算出了逆序數。所以這就是為什麼很多人會將兩者相提並論的原因，也是我個人非常喜歡這個問題的原因。看起來完全不相關的兩個問題，竟然能用幾乎同一套程式碼來解決，不得不感嘆演算法的神奇。也正是因此，我們這些演算法的研究和學習者，才能獲取到源源不斷的樂趣。
今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支援是我最大的動力。
