归并排序 mergeSort
把序列按长度分成两个子序列,每个子序列再次分解,重复以上操作直至无法分解(递归从外到内的过程)
把两个最小单位的子序列按条件归并成一个新序列,新序列继续和同一层的序列归并(递归从内到外的过程)
使用两个指针从被归并的两个序列中分别取值比较大小,取出满足条件的值并移动该指针,然后进行下一次比较
利用map()、reduce()进行拆解和合并的过程
需要消耗大量空间
复杂度:最优时间复杂度:O(nlogn)
最差时间复杂度:O(nlogn)
稳定性:稳定
def merge_sort(varlist):
# 结束递归的条件,子序列被分解为单个元素
if len(varlist) <= 1 :
return varlist
# 1.第一步:把完整的序列分解为单个元素的序列,然后作为参数调用归并两两排序
# 将序列按长度等分
num = len(varlist) // 2
l_left = varlist[:num]
l_right = varlist[num:]
# 分解后的两个子序列调用自身继续分解,直至被分解为单个元素
left = merge_sort(l_left)
right = merge_sort(l_right)
# 当出现left和right都为单个元素时,递归从外向内的过程结束,开始归并
return merge(left,right)
def merge(left,right):
# 2.第二步:从传入的两个序列中,按顺序各取出一个元素比较大小
# 把满足排序条件的取出放入空list,不满足的等待下一次比较,直至任一序列中元素被取完
# l和r指针用来标记从left和right中取值的位置
l,r = 0,0
# 空list用来存放排序后的结果,排序完成则return
reslist = []
# l增加到与left长度相等,或r增加到与right长度相等,表示该序列被遍历完成,结束循环
while l < len(left) and r < len(right) :
# 从两个序列中各取出一个值进行比较,把满足条件的放入新序列,并移动指针
if left[l] < right[r] :
reslist.append(left[l])
l += 1
else :
reslist.append(right[r])
r += 1
# 把另一序列中剩余的元素全部添加到新序列
# 此时另一个序列中无论剩余多少元素没被取出,都一定是在前一层归并中排好序的
reslist += left[l:]
reslist += right[r:]
return reslist
varl = [5,1,7,5,6,3,4,8,2,3,5,9]
res = merge_sort(varl)
print(res)
[1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9]