Python程式設計中歸併排序演算法的實作步驟詳細介紹

基本思想：歸併排序是一種典型的分治思想，把一個無序列表一分為二，對每個子序列再一分為二，繼續下去，直到無法再進行劃分為止。然後，就開始合併的過程，將每個子序列和另外一個子序列的元素進行比較，依序把小元素放入結果序列中合併，最後完成歸併排序。

歸併操作過程：

申請空間，使其大小為兩個已排序序列總和，該空間用來存放合併後的序列
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置
重複步驟3直到某一指標達到序列尾
將另一序列剩下的所有元素直接複製到合併序列尾
上述說法是理論表述，下面用一個實際例子說明：

例如一個無序數組

[6,2,3,1,7]

首先將這個陣列透過遞歸方式分解，直到：

[6],[2],[3],[1],[7]

然後開始合併排序，也是用遞迴的方式進行：

兩個兩個合併排序，得到：

[2,6],[1,3],[7]

上一步中，其實也是按照本步驟的方式合併的，只不過由於每個list中一個數，不能完全顯示過程。下面則可以完全顯示過程。

初始：

 a = [2,6] b = [1,3] c = []

第1步，順序從a,b取出一個數字：2,1 比較大小後放入c中，並將該數字從原list中刪除，結果是：

a = [2,6] b = [3] c = [1]

第2步，繼續從a,b中依照順序取出數字，也就是重複上面步驟，這次是：2,3 比較大小後放入c中，並將該數字從原list中刪除，結果是：

a = [6] b = [3] c = [1,2]

#第3步,再重複前邊的步驟,結果是：

a = [6] b = [] c = [1,2,3]

最後一步，將6追加到c中，結果形成了：

a = [] b = [] c = [1,2,3,6]

透過重複應用上面的流程，實現[1,2,3,6]與[7]的合併

最終得到排序結果

[1,2,3,6,7]

本文列舉了三種python的實作方法：

方法1：將前面講述的過程翻譯過來了，略先拙笨

#! /usr/bin/env python
#coding:utf-8

def merge_sort(seq):
 if len(seq) ==1:
 return seq
 else:
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])

 i = 0 #left 计数
 j = 0 #right 计数
 k = 0 #总计数

 while i < len(left) and j < len(right):
  if left[i] < right [j]:
  seq[k] = left[i]
  i +=1
  k +=1
  else:
  seq[k] = right[j]
  j +=1
  k +=1

 remain = left if i<j else right
 r = i if remain ==left else j

 while r<len(remain):
  seq[k] = remain[r]
  r +=1
  k +=1

 return seq

方法2：在依照順序取數值方面，應用了list.pop()方法，程式碼更緊湊簡潔

#! /usr/bin/env python
#coding:utf-8


def merge_sort(lst): #此方法来自维基百科

 if len(lst) <= 1:
 return lst

 def merge(left, right):
 merged = []

 while left and right:
  merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))

 while left:
  merged.append(left.pop(0))

 while right:
  merged.append(right.pop(0))

 return merged

 middle = int(len(lst) / 2) 
 left = merge_sort(lst[:middle])
 right = merge_sort(lst[middle:])
 return merge(left, right)

方法3：原來在python的模組heapq中就提供了歸併排序的方法，只要將分解後的結果導入方法即可。

#! /usr/bin/env python
#coding:utf-8


from heapq import merge

def merge_sort(seq):
 if len(seq) <= 1:
 return m
 else:  
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])
 return list(merge(left, right))  #heapq.merge()

if __name__=="__main__":
 seq = [1,3,6,2,4]
 print merge_sort(seq)

更多Python程式設計中歸併排序演算法的實作步驟詳細介紹相關文章請關注PHP中文網！