歸并排序
歸并排序演算法的核心就是 “歸并”，將兩個有序的數列合并，形成更大的有序陣列，
歸并排序的原理
上面說了，歸并排序的核心就是“歸并”，如果排序一個陣列，那么將陣列從中間分成前后兩部分，對前后兩部分分別進行排序，然后再將排序好的合并在一起，那么這樣整個陣列就會成為更大的有序陣列，例如下面示圖：
歸并排序使用的思想是分治思想，即是分而治之，將復雜問題分解成兩個或者多個規模相同或類似的子問題，然后繼續細化，當子問題足夠簡單，能夠被求解，那么復雜的問題也就能夠被求解出來，
這里跟遞回的思想很像，遞回也是將大問題細化為小問題，找出終止條件和遞推公式，分治演算法一般都是用遞回實作的，分治的思想是一種解決問題的處理思想，遞回是一種編程技巧，兩者不會沖突，
上面說了，歸并排序能夠使用遞回實作，那么現在先寫出遞推公式和終止條件，
# 遞推公式
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] 中，現在主要的問題是如何實作分解后排序合并？
先用一個簡單的示例，如下示圖：
先申請臨時陣列 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
以上本篇幅就是關于歸并排序的主要內容，
歡迎關注微信公眾號《書所集錄》
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/151088.html
標籤：Python
上一篇：Python中List的排序