歸併排序python實現

• 2020 年 1 月 16 日
• 筆記

歸併排序python實現

歸併排序

歸併排序在於把序列拆分再合併起來，使用分治法來實現，這就意味這要構造遞歸演算法

首先是一個例子

原序先通過一半一半的拆分，然後：

然後再一步一步的向上合併，在合併的過程中完成了排序，合併排序演算法如下：

def merge(s1,s2,s):      """將兩個列表是s1，s2按順序融合為一個列表s,s為原列表"""      # j和i就相當於兩個指向的位置，i指s1，j指s2      i = j = 0      while i+j<len(s):          # j==len(s2)時說明s2走完了，或者s1沒走完並且s1中該位置是最小的          if j==len(s2) or (i<len(s1) and s1[i]<s2[j]):              s[i+j] = s1[i]              i += 1          else:              s[i+j] = s2[j]              j += 1

這是以列表為例，道理其實很簡單，因為兩個序列是排好序的，所以都從左往右，互相比較選擇較小的那個數放入最後的序列，s是原序列，所以在一開始會有與len(s)的比較

完整演算法

演算法中通過遞歸併調用merge函數完成排序

def merge(s1,s2,s):      """將兩個列表是s1，s2按順序融合為一個列表s,s為原列表"""      # j和i就相當於兩個指向的位置，i指s1，j指s2      i = j = 0      while i+j<len(s):          # j==len(s2)時說明s2走完了，或者s1沒走完並且s1中該位置是最小的          if j==len(s2) or (i<len(s1) and s1[i]<s2[j]):              s[i+j] = s1[i]              i += 1          else:              s[i+j] = s2[j]              j += 1    def merge_sort(s):      """歸併排序"""      n = len(s)      # 剩一個或沒有直接返回，不用排序      if n < 2:          return      # 拆分      mid = n // 2      s1 = s[0:mid]      s2 = s[mid:n]      # 子序列遞歸調用排序      merge_sort(s1)      merge_sort(s2)      # 合併      merge(s1,s2,s)    if __name__ == '__main__':      s = [1,7,3,5,4]      merge_sort(s)      print(s)

時間複雜度

還拿這個圖說

這個圖顯然是二叉樹的形式，所以若集合有n個元素，那高度就為log(n)

但其實在每一層做比較的時候，都是一個一個的向序列中放小的元素，每一層都是要放n次

所以時間複雜度為nlog(n)

​