一、學習要點：
解決問題的思路：
根據分治思想設計程序時的思維過程：
1.一定是先找到最小問題規模時的求解方法
2.然后考慮隨著問題規模增大時的求解方法
3.找到求解過程的遞歸函數式后，設計遞歸程序即可
demo 分析：
seq=[5,3,2,0,1,4]
1.首先找到最小規模時的求解方法：
當列表中只有一個元素的時候，就是最小規模。
如：
left=[5],right=[3]
將兩個列表合并成一個有序的列表：
result=[]
if left[0]<=right[0]:
result.append(left[0])
else:
result.append(right[0])
result+=left此時 合并后的列表 result=[3,5]就是排序好的列表。
2.規模擴大
left=[0,3,5] right=[1,4]
將兩個有序列表，合并成一個有序列表：
比較二個列表的第一個數，誰小就先取誰，取了后就在對應的列表中跳過這個數。然后再進行比較，如果有空，那就將另一個列表的數據依次取出即可：
result=[]
i=0
j=0
while i<len(left) and j<len(right):
if left[i]<=right[j]:
result.append(left[i])
i+=1
else:
result.append(right[j])
j+=1
result+=left[i:]
result+=right[j:]
3.設計遞歸，將復雜的問題分解為最小規模子問題。
二、代碼：

def mergesort(seq):"""歸并排序"""if len(seq) <= 1:return seqmid = len(seq) / 2 # 將列表分成更小的兩個列表# 分別對左右兩個列表進行處理，分別返回兩個排序好的列表left = mergesort(seq[:mid])right = mergesort(seq[mid:])# 對排序好的兩個列表合并，產生一個新的排序好的列表return merge(left, right)def merge(left, right):"""合并兩個已排序好的列表，產生一個新的已排序好的列表"""result = [] # 新的已排序好的列表i = 0 # 下標j = 0# 對兩個列表中的元素 兩兩對比。# 將最小的元素，放到result中，并對當前列表下標加1while i < len(left) and j < len(right):if left[i] <= right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result += left[i:]result += right[j:]return resultseq = [5,3,0,6,1,4] print '排序前：',seq result = mergesort(seq) print '排序后：',result```三、運行結果：  四：如看不懂，參考原博客： https://www.jianshu.com/p/3ad5373465fd

總結

以上是生活随笔為你收集整理的归并排序（python实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。