Python归并排序实例
1、打开Python开发工具IDLE,新建‘归并.py’文件，并写代码如下：
def guibing(list1):
n = len(list1)
print (list1)
if n==1:
return
half = n//2
guibing(list1[:half])
guibing(list1[half:])
if __name__ == '__main__':
list1 = [7,9,3,4]
guibing(list1)
这是将传入的list进行拆分，拆分的目的是形成单个元素，再组合成有序列表
2、F5运行程序，可以看到传入list逐级拆分的过程，各过程列表分别如下：
[7, 9, 3, 4]
[7, 9]
[7]
[9]
[3, 4]
[3]
[4]
3、继续编写代码，先将拆分的列表组合，代码如下：
def guibing(list1):
n = len(list1)
print (list1)
if n==1:
return list1
half = n//2
left_res = guibing(list1[:half])
right_res = guibing(list1[half:])
return left_res+right_res
if __name__ == '__main__':
list1 = [7,9,3,4]
guibing(list1)
print (list1)
4、F5运行程序，拆分的列表又重新组合，但是这里并没有进行排序，下一步我们写一个简单的排序函数。
5、针对拆分的列表进行排序，代码如下：
def guibing(list1):
n = len(list1)
print (list1)
if n==1:
return list1
half = n//2
left_res = guibing(list1[:half])
right_res = guibing(list1[half:])
return mergersort(left_res,right_res)
def mergersort(a,b):
c=[]
llen = len(a)
rlen = len(b)
h =0
j=0
while j< llen and h< rlen :
if a[j]<b[h]:
c.append(a[j])
j+=1
else:
c.append(b[h])
h+=1
if j == len(a): #这里不能简单比较a、b长度
for i in b[h:]:
c.append(i)
else:
for i in a[j:]:
c.append(i)
return c
if __name__ == '__main__':
list1 = [7,9,3,4,5,8]
print (guibing(list1))
#print (list1)
6、F5运行程序，排序正常，注意这里不能再打印传入的list，因为返回的是新列表