Python編程中歸并排序算法的實(shí)現(xiàn)步驟詳解

基本思想：歸并排序是一種典型的分治思想，把一個(gè)無(wú)序列表一分為二，對(duì)每個(gè)子序列再一分為二，繼續(xù)下去，直到無(wú)法再進(jìn)行劃分為止。然后，就開(kāi)始合并的過(guò)程，對(duì)每個(gè)子序列和另外一個(gè)子序列的元素進(jìn)行比較，依次把小元素放入結(jié)果序列中進(jìn)行合并，最終完成歸并排序。

歸并操作過(guò)程：
申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針達(dá)到序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
上述說(shuō)法是理論表述，下面用一個(gè)實(shí)際例子說(shuō)明：
例如一個(gè)無(wú)序數(shù)組    
[6,2,3,1,7]

首先將這個(gè)數(shù)組通過(guò)遞歸方式進(jìn)行分解，直到：    
[6],[2],[3],[1],[7]

然后開(kāi)始合并排序，也是用遞歸的方式進(jìn)行：

兩個(gè)兩個(gè)合并排序，得到：    
[2,6],[1,3],[7]

上一步中，其實(shí)也是按照本步驟的方式合并的，只不過(guò)由于每個(gè)list中一個(gè)數(shù)，不能完全顯示過(guò)程。下面則可以完全顯示過(guò)程。

初始：    
a = [2,6] b = [1,3] c = []

第1步，順序從a,b中取出一個(gè)數(shù)字：2,1 比較大小后放入c中，并將該數(shù)字從原list中刪除，結(jié)果是：    
a = [2,6] b = [3] c = [1]

第2步，繼續(xù)從a,b中按照順序取出數(shù)字，也就是重復(fù)上面步驟，這次是：2,3 比較大小后放入c中，并將該數(shù)字從原list中刪除，結(jié)果是：    
a = [6] b = [3] c = [1,2]

第3步,再重復(fù)前邊的步驟,結(jié)果是：    
a = [6] b = [] c = [1,2,3]

最后一步，將6追加到c中，結(jié)果形成了：    
a = [] b = [] c = [1,2,3,6]

通過(guò)反復(fù)應(yīng)用上面的流程，實(shí)現(xiàn)[1,2,3,6]與[7]的合并

最終得到排序結(jié)果    
[1,2,3,6,7]

本文列舉了三種python的實(shí)現(xiàn)方法：

方法1：將前面講述的過(guò)程翻譯過(guò)來(lái)了，略先拙笨    
#! /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ì)數(shù)
 j = 0 #right 計(jì)數(shù)
 k = 0 #總計(jì)數(shù)
 
 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：在按照順序取數(shù)值方面，應(yīng)用了list.pop()方法，代碼更緊湊簡(jiǎn)潔    
#! /usr/bin/env python
#coding:utf-8
 
 
def merge_sort(lst): #此方法來(lái)自維基百科
 
 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：原來(lái)在python的模塊heapq中就提供了歸并排序的方法，只要將分解后的結(jié)果導(dǎo)入該方法即可。    
#! /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)