Python编程中归并排序算法的实现步骤详解
基本思想:归并排序是一种典型的分治思想,把一个无序列表一分为二,对每个子序列再一分为二,继续下去,直到无法再进行划分为止。然后,就开始合并的过程,对每个子序列和另外一个子序列的元素进行比较,依次把小元素放入结果序列中进行合并,最终完成归并排序。 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 例如一个无序数组 [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,3] 最后一步,将6追加到c中,结果形成了: a = [] b = [] c = [1,6] 通过反复应用上面的流程,实现[1,6]与[7]的合并 最终得到排序结果 [1,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,4] print merge_sort(seq) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |