1.归并排序介绍
1.归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
2.将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。
3.然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
2. 代码实现
def merge_sort(lst):
"""归并排序"""
if len(lst) <= 1:
return lst
mid = len(lst) // 2
# 二分分解
# left 采用归并排序后形成的有序的新的列表
left_lst = merge_sort(lst[:mid])
# right 采用归并排序后形成的有序的新的列表
right_lst = merge_sort(lst[mid:])
# 将两个有序的子序列合并成一个新的整体
return merge(left_lst,right_lst)
def merge(left_lst, right_lst):
'''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
#left与right的下标指针
left_pointer , right_pointer = 0 , 0
result = []
while left_pointer < len(left_lst) and right_pointer < len(right_lst):
if left_lst[left_pointer] < right_lst[right_pointer]:
result.append(left_lst[left_pointer])
left_pointer += 1
else:
result.append(right_lst[right_pointer])
right_pointer += 1
# 退出循环体之后，表示左右两个列表至少有一个列表中数据全部取完，让另一个列表中剩余的元素全部取出来
result += left_lst[left_pointer:] # 将左边列表剩余的追加上去
result += right_lst[right_pointer:] # 将右边列表剩余的追加上去
return result # 将新排序过的列表返回回去
if __name__ == '__main__':
alist = [54,26,93,17,77,31,44,55,20]
print(alist)
sorted_alist = merge_sort(alist)
print(alist)
print(sorted_alist)
# 代码运行结果
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
