本文共 1461 字，大约阅读时间需要 4 分钟。

python实现归并排序

归并排序：

思路分析：

（1）归并排序就是先进行分解操作，再进行合并操作

（2）当分解到最小以后，就进行合并，合并的同时比较两两数组之间的大小将其排序好 （3）这样的分解时需要用递归来实现的。 (4)如果排序元素是奇数个，辣么对于最后一个数字的处理。

代码实现：

def merge_sort(alist):    """归并排序"""    n=len(alist)    if n <=1:        return alist    mid=n//2        #left采用归并排序后形成的有序的新的列表    left_list=merge_sort(alist[:mid])        #right采用归并排序后形成的有序的新的列表    right_list=merge_sort(alist[mid:])    #完成拆分过程。#将两个有序子序列合并成一个新的整体#merge(left,right)    left_pointer,right_pointer=0,0 #需要左指针右指针指向新的列表开头用于排序    result=[]  #用于存储新的排序列表    while left_pointer

代码分析：

根据分析的思路，我们可以就得知：

（1）分解操作： 首先我们要晓得列表中间的元素，辣么就用mid=n//2记录，然后通过递归方式进行拆分，当进行到长度小于或者等于零的时候就停止拆分工作。==这里需要注意的是：==我们操作的不在是同一个列表，是不同的一块一块的列表了，因此我们需要变量来记录，因此会出现left_list， right_list。最后递归的终止条件也是要返回列表的。 （3）重新组合： 我们定义两个变量来指向每一个列表的头（ left_pointer,right_pointer=0,0 ）。比较左右列表之间的大小关系（我们以从小到大方式为例），如果左边元素小就追加到一个新的result里面去，同时指针向后移动，反之，将右边追加到result，并移动指针。循环操作的条件是两个指针都是小于原来指向列表的长度的时候，进行循环操作。 （4）对于最后一个数字的处理：

实例分析：

_[54,26,93,17,77,31,44,55]

(1)进入merge_sort(a),

(2)执行left_list=merge_sort(alist[:mid])操作。 left_list=[54,26,93,17] left_list=[54,26] left_list=[54] 此时n1所以退出left_list=merge_sort(alist[:mid])循环，并return[54]

(3)然后执行 right_list=merge_sort(alist[mid:])操作

right_list=[26]

此时n1所以退出 right_list=merge_sort(alist[mid:])循环，并return[26] (4)此时执行合并算法 返回[26,54] 此时此刻对于left_list=[54,26,93,17] 来说已经完成了左边排序的操作，后面进行right_list=[93,17] 操作，操作过程同上类似，最后返回[17,93] (5)此时此刻，我们完成了[54,26,93,17,77,31,44,55]左边的算法，后面就同时进项右边操作，[77,31,44,55],一部一部按照代码和递归思想进行操作

时间复杂度：

转载地址：http://prgzi.baihongyu.com/