归并排序也是只听说，没看过算法的代码也没写过，昨天晚上看了下归并排序的思想，似乎是一个我可以驾驭的递归，于是就准备自己手写
本文主要记录一下我写归并的历程，博友可以直接跳到最终版
先写上我的思路（写递归最重要的就是思路，以前总喜欢画栈的结构图来构思，现在才发现这只是写递归的必备基础，而非方法，所以我这次举一个简单的列表，直接根据数据流动（网站开发的习惯）来确定思路，顺便还能考虑下所有特殊情况）
再附上我的代码（写了几个小时候我还是崩溃了）
1 def merge_sort(clist,low,high): 2 mid = (high + low + 1) // 2 3 if len(clist)>1: # 进行拆分 4 glist = [] 5 for item in range(low, high+1): 6 glist.append(clist[item]) 7 left_list = merge_sort(glist, low, mid - 1) 8 right_list = merge_sort(glist, mid, high) 9 # 合并 10 return merges(left_list, right_list) 11 else: 12 return clist 13 29 # 将俩个等长有序的列表合并=>插入排序好些，还是有些亏，浪费了第二个列表等长有序的属性了 30 def merges(firstList,secondList): 31 length=len(firstList) 32 reList=[] 33 j=0 34 i=0 35 while i<length or j<length: 36 if i>=length: 37 reList.append(secondList[j]) 38 j+=1 39 elif j>=length: 40 reList.append(firstList[i]) 41 i+=1 42 else: 43 if firstList[i]<secondList[j]: 44 reList.append(firstList[i]) 45 i+=1 46 else: 47 reList.append(secondList[j]) 48 j+=1 49 return reList 50 51 if __name__=="__main__": 52 cclist=[54,26,93 ,17,77,31,44,55,20] #,17,77,31,44,55,56 53 print(merge_sort(cclist,0,len(cclist)-1)) 54 57 # ===>崩溃
写到这里，debug时发现high到最后会为-1，显示是不对的，但low，high，mid这三个参数怎么调，glist拆分为左右俩个列表时总是有索引越界的问题
附上改正后的代码=》申请俩个独立的列表，在某种程度上说是low，high与mid的解耦，当时的想法是：low固定为0后，只要合理设置high的值就行了，同时mid的值也无需分情况讨论，但是多申请一个列表会浪费空间吗？
答案是不会的，因为反正需要存储clist的所有元素，用俩个列表只是分两次存储罢了。
改后的代码（还是有一些瑕疵，因为申请两个列表完全可以通过且列表切片得到，merges不需要改变）
def merge_sort(clist): n=len(clist) if n>1: mid = n// 2 l_list = [] r_list=[] for item in range(0, n): if item<mid: l_list.append(clist[item]) else: r_list.append(clist[item]) left_list = merge_sort(l_list) right_list = merge_sort(r_list) # 合并 return merges(left_list, right_list) else: return clist
最后附上最终版（用了分片明显感觉就很舒服）
def mergeSort(clist): """"归并排序""" n=len(clist) if n<=1: return clist mid=n//2 left_list=mergeSort(clist[:mid]) # 可以通过切片而非循环来确认左右列表 right_list = mergeSort(clist[mid:]) return merges(left_list,right_list)
回顾整个过程：有个错误一直没有深究，导致我如此崩溃，我曾经想过用俩个列表拆分传入的clist，但是莫名其妙地就感觉这样会浪费空间，感觉通过一个列表和low，high两个索引同样可以实现划分左右列表的目的，但其实这样需要考虑很多情况，考虑到最后就崩溃了。而如果我深入思考一步，不是下意识地认为，就能很愉快地完成归并了。