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/envpython #coding:utf-8 defmerge_sort(seq): iflen(seq)==1: returnseq else: middle=len(seq)/2 left=merge_sort(seq[:middle]) right=merge_sort(seq[middle:]) i=0#left计数 j=0#right计数 k=0#总计数 whilei<len(left)andj<len(right): ifleft[i]<right[j]: seq[k]=left[i] i+=1 k+=1 else: seq[k]=right[j] j+=1 k+=1 remain=leftifi<jelseright r=iifremain==leftelsej whiler<len(remain): seq[k]=remain[r] r+=1 k+=1 returnseq
方法2：在按照顺序取数值方面，应用了list.pop()方法，代码更紧凑简洁
#!/usr/bin/envpython #coding:utf-8 defmerge_sort(lst):#此方法来自维基百科 iflen(lst)<=1: returnlst defmerge(left,right): merged=[] whileleftandright: merged.append(left.pop(0)ifleft[0]<=right[0]elseright.pop(0)) whileleft: merged.append(left.pop(0)) whileright: merged.append(right.pop(0)) returnmerged middle=int(len(lst)/2) left=merge_sort(lst[:middle]) right=merge_sort(lst[middle:]) returnmerge(left,right)
方法3：原来在python的模块heapq中就提供了归并排序的方法，只要将分解后的结果导入该方法即可。
#!/usr/bin/envpython #coding:utf-8 fromheapqimportmerge defmerge_sort(seq): iflen(seq)<=1: returnm else: middle=len(seq)/2 left=merge_sort(seq[:middle]) right=merge_sort(seq[middle:]) returnlist(merge(left,right))#heapq.merge() if__name__=="__main__": seq=[1,3,6,2,4] printmerge_sort(seq)