递归算法是直接或者间接不断反复调用自身来达到解决问题的方法。这就要求原始问题可以分解成相同问题的子问题。而分治（divide and conquer ，D&C）就是将待解决复杂的问题能够简化为几个若干个小规模相同的问题，然后逐步划分，达到易于解决的程度。
分治算法适用问题的特征有
• 该问题的规模缩小到一定的程度就可以容易地解决
• 该问题可以分解为若干个规模较小的相同问题 、子问题规模相同
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
因此，递归算法和分治算法可以说是相得益彰。
归并排序（又称合并排序）是分治算法的一个完美列子。它的基本思想是对于一个需要排序的数组，算法首先把它分为两个部分，并对每个子数组进行递归排序（将子序列继续分解，直到子序列包含的元素个数为1，因为单个元素的序列本身是有序的），最后把这两个排序好的子数组合并为一个有序数组。如下一个数组的排序的例子
不难写出伪代码如下
mergesort(alist):
n= len(alist)
if n>1:
copyalist[0:n//2+1] to blist
copyalist[n//2+1:n] to clist
mergesort(blist)
mergesort(clist)
merge(blist,clist,alist)
其中merge方法是合并算法，目的是将分解后的排序好的子数组进行合并排序。
该算法中用两个指针（下标）分别指向两个待合并数组的第一个元素，然后比较这两个元素的大小，将较小的元素添加到一个新创建的辅助数组中，接着被复制数组中的指针后移，指向下一个元素，上述操作一直持续到两个数组中有一个被先处理完毕为止，然后在未处理完的数组中，剩下的元素被复制到新数组的尾部即可。如
故python实现代码为
def mergesort(alist):
length=len(alist)
if length<=1: #基础条件，只有一个元素时
return
else:
blist=alist[0:length//2]
clist=alist[length//2::]
mergesort(blist)
mergesort(clist)
merge(blist,clist,alist)
def merge(blist,clist,tlist):
blen=len(blist)
clen=len(clist)
bi=ci=k=0
while bi排序
if blist[bi]<=clist[ci]:
tlist[k]=blist[bi];
bi+=1
else:
tlist[k]=clist[ci];
ci+=1
k=k+1
tlist[k:blen+clen]= bi==blen and clist[ci:clen] or blist[bi:blen] #blist先遍历完，clist直接追加到tlist
测试用例
>>> alist=[2,1]
>>> mergesort(alist)
>>> alist
[1, 2]
>>> alist=[2,1,0,5,3]
>>> mergesort(alist)
>>> alist
[0, 1, 2, 3, 5]
>>>
合并排序的时间复杂度与快速排序一样。只不过需要额外的存储空间来进行合并，每调用一次合并算法，都需要临时分配一个适当大小的辅助存储区，最多分配大小为n。因为递归调用时占用的帧空间是递归树的深度n=[if !msEquation] [endif]，则x=logn，递归树的深度是logn。
网友评论