本文章的所有代码和相关文章， 仅用于经验技术交流分享，禁止将相关技术应用到不正当途径，滥用技术产生的风险与本人无关。 本文章是自己学习的一些记录。
开始
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
代码
def merge_sort(alist
):
'''归并排序算法'''
n
=len(alist
)
if n
<=1:
return alist
mid
=n
//2
left_li
=merge_sort
(alist
[:mid
])
right_li
=merge_sort
(alist
[mid
:])
'''因为alist[:mid]不包含mid,alist[mid:]包含mid,所以全部的元素都包含进来'''
left_cur
,right_cur
=0,0
result
=[]
while left_cur
<len(left_li
) and right_cur
<len(right_li
):
if left_li
[left_cur
]<right_li
[right_cur
]:
result
.append
(left_li
[left_cur
])
left_cur
+=1
else:
result
.append
(right_li
[right_cur
])
right_cur
+=1
result
+=left_li
[left_cur
:]
result
+=right_li
[right_cur
:]
return result
if __name__
== '__main__':
li
= [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li
)
merge_sort_li
=merge_sort
(li
)
print(li
)
print(merge_sort_li
)
思路： 归并排序算法的主要思路就是将一个序列不断的拆分，然后拆分到只有一个元素的序列，然后进行合并，合并的规则是小的在前，大的在后的原则； 然后循环这样的合并排序，序列大于一个元素的时候借助游标来滑动进行排序； 直到游标滑倒拆分两部分分最末尾的位置； 将剩下元素添加到一个列表result，排序结束; 总之就是一级一级的嵌套，然后合并，返回列表，退出嵌套的过程。
时间复杂度
整体的时间复杂度的计算就是用横向的执行步骤n *拆分的步骤，拆分是logn，也可以看成是纵向的拆分的步骤，整体的相乘就是时间复杂度的计算
最优时间复杂度： 最坏时间复杂度：
常见的排序算法的效率的比较：
参考资料：传智播客数据结构
