演算法 | 歸併排序

  • 2020 年 4 月 30 日
  • 筆記

歸併排序


歸併排序演算法的核心就是 「歸併」,將兩個有序的數列合併,形成更大的有序數組。

歸併排序的原理


上面說了,歸併排序的核心就是「歸併」。如果排序一個數組,那麼將數組從中間分成前後兩部分,對前後兩部分分別進行排序,然後再將排序好的合併在一起,那麼這樣整個數組就會成為更大的有序數組。例如下面示圖:

歸併排序分解圖例

歸併排序使用的思想是分治思想,即是分而治之。將複雜問題分解成兩個或者多個規模相同或類似的子問題,然後繼續細化,當子問題足夠簡單,能夠被求解,那麼複雜的問題也就能夠被求解出來。

這裡跟遞歸的思想很像。遞歸也是將大問題細化為小問題,找出終止條件和遞推公式。分治演算法一般都是用遞歸實現的。分治的思想是一種解決問題的處理思想,遞歸是一種編程技巧,兩者不會衝突。

上面說了,歸併排序能夠使用遞歸實現,那麼現在先寫出遞推公式和終止條件。

# 遞推公式
merge_sort(a...b) = merge(merge_sort(a...k), merge_sort(k+1, b))

# 終止條件
a >= b,不再繼續分解

這裡解釋下上面的公式,終止條件不細講,這裡表示的,索引 a 大於等於 索引 b,即是已經到達數組末尾,不能夠再細分。

講下遞推公式,merge_sort(a...b),表示給索引 a 到 k 之間的數組進行排序。這裡將分體轉為為兩個子問題,merge_sort(a...k)merge_sort(k+1...b),其中 k 表示原數組中間的位置。而 merge() 函數表示當兩個將兩個排好序的子數組合併,這樣就能夠使原數組實現排序。

現在將這個遞推公式轉化為程式碼(這裡使用偽程式碼):

# nums 表示數組,a 為起始點,b 為數組末尾索引
def merge_sort(nums, a, b):
    # 終止條件
    if a >= b:
        return
    
    # 取中間位置
    k = (a + b) // 2
    # 分治遞歸
    merge_sort(nums, a, k)
    merge_sort(nums, k+1, b)
    merge(nums[a...b], nums[a...k], nums[k+1, b])

最後 merge() 函數的作用,就是將後面兩個子數組合併好後放到 nums[a…b] 中。現在主要的問題是如何實現分解後排序合併?

先用一個簡單的示例,如下示圖:

merge

先申請臨時數組 temp,定義指針 i,j 分別指向 兩個子數組的第一個元素。比較 nums[i],nums[j],較小的元素放入臨時數組中,同時該元素的指針向右移動。

循環上面的過程,直到其中一個子數組的所有數據都放入臨時數組中,這個時候,將另外一個數組剩下的部分也放到臨時數組中。這個臨時數組就是最終合併的結果,將其複製回原數組即可。

現在用偽程式碼實現這個過程:

def merge(nums[a...b], nums[a...k], nums[k+1, b]):
    # length 表示數組大小
    temp = [0] * length

    # 初始化指針,i, j, ti
    i, j, ti, = a, k+1, 0
    # 取小值放入臨時數組中,
    while (i <= k and j <= b):
        if (nums[i]<=nums[j]):
            temp[ti]=nums[i]
            i+=1
        else:
            temp[ti]=nums[j]
            j+=1
        ti+=1

    # 合併時會出現一個數組全部放入臨時數組中,
    # 另外一個數組還有剩餘,這裡將剩餘部分也放到臨時數組中
    if i < nums[a...k].length:
        for x in range(i, nums[a...k].length):
            temp[ti] = nums[x]
            ti += 1
    else:
        for x in range(j, nums[k+1...b].length):
            temp[ti] = nums[x]
            ti += 1

    # 如果需要複製回原數組,也可以直接複製
    return temp

以上本篇幅就是關於歸併排序的主要內容。


歡迎關注微信公眾號《書所集錄》