《专业技术学习笔记》清未

1、算法 归并排序

　　对数组进行排序，按从小到大的顺序排,归并排序算法采用递归的思想

　　基础情景是对两个只有一个元素的数组进行排序，小的在前、大的在后，将两个单元素数组合并组成一个从小到大顺序的2元素数组

　　然后再拿这个2元素数组A与另一个2元素数组B进行合并，两个数组同时从左到右遍历，组成四个元素的数组C，选取A和B的第一个元素里较小的那个作为C的第一个元素，较大的那个作为C的第二个元素，以此类推

　　语言：python

　　def Mergesort(list）：
　　if len(list)==1:
　　return [list]//基础情境

　　else:
　　Combine_list=[]
　　list1=Mergesort(list[0:int(len(list)/2)])
　　list2=Mergesort(list[int(len(list)2):len(list)]
　　i=j=0
　　l_i=len(list1) l_j=len(list2)
　　while(i!=l_i and j!=l_j):
　　while(i 小于 l_i and j小于l_j and list1[i]大于list2[j]):
　　Combine_list.append(list2[j])
　　j+=1
　　while(i小于l_i and j小于l_j and list1[i]小于等于list2[j]):
　　Combine_list.append(list1[i])
　　i+=1
　　if i!=l_i:
　　for x in range(i,l_i):
　　Combine_list.append(list1[x])
　　if j!=l_j:
　　for x in range(j,l_j):
　　Combine_list.append(list2[x])
　　return Combine_list

　　这种方法不是最优解，因为每次递归调用时都会生成一个临时的Combine_list，递归次数一多，空间开销就会很大，最优解应该是不用生成临时Combine_list也能达到效果，这个等我有时间再继续深入研究