python数据结构与算法—

python数据结构与算法——归并排序

归并排序：

原理与C语言实现

参考：白话经典算法系列之五归并排序的实现

1. 容易对有序数组A,B进行排序。

2. 为了使得A,B组内数据有序：可以将A，B组各自再分成二组。

3. 经过不断分组，当分出来的小组只有一个数据时(有序)，合并相邻二个小组。

这样通过先递归的分解数列，再合并数列就完成了归并排序。

代码摘自《Python Algorithm》

 1 # 对数组seq进行归并排序
 2 # 返回排序后数组
 3 def mergesort(seq):
 4     mid = len(seq)//2
 5     lft, rgt = seq[:mid], seq[mid:]
 6     if len(lft) > 1: lft = mergesort(lft)       # 对数组的一半进行排序
 7     if len(rgt) > 1: rgt = mergesort(rgt)
 8 
 9     res = []
10     # lft，rgt 均按递增排列
11     while lft and rgt:                          # 左右数组均不为空 
12         if lft[-1] >= rgt[-1]:                  # 找出两个数组中最大的元素
13             res.append(lft.pop())               # 放入结果数组中，并将原数组元素删除
14         else:
15             res.append(rgt.pop())               # 如果用pop(0)则下面的res不用反转，但是pop(0)时间慢
16                                                 # 而res相对较快
17     # res开始时为一个递减数组，将其反转使之递增
18     res.reverse()
19     return (lft or rgt) + res                   # 将余下的有序数组拼接到res前
20 
21 seq = [1,2,4,6,3,7,5,9,0,5,7]
22 print mergesort(seq)