归并排序
def mergeSort(alist):
if len(alist) > 1:
#基本结束条件,当len=1时,直接不走if内的模块,直接return
mid = len(alist) // 2
leftlist = alist[:mid]
rightlist = alist[mid:]
mergeSort(leftlist)
mergeSort(rightlist)
i = j = k = 0
while i < len(leftlist) and j < len(rightlist):
if leftlist[i] < rightlist[j]:
alist[k] = leftlist[i]
i += 1
else:
alist[k] = rightlist[j]
alist[k] = rightlist[j]
j += 1
k += 1
while i < len(leftlist):
alist[k] = leftlist[i]
i += 1
k += 1
while j < len(rightlist):
alist[k] = rightlist[j]
j += 1
k += 1
return alist
书上说:
最后, 我们还是注意到两个切片操作为了时间复杂度分析精确起见,可以通过取消切片操作,改为传递两个分裂部分的起始点和终止点,也是没问题的,只是算法可读性稍微牺牲一点点。