python算法(五)归并排序
归并排序
问题:将一组乱序排列的数列,按从小到大(从大到小)的顺序重新排序.
解决问题的逻辑:
归并排序的逻辑是:
在这里插入图片描述
代码实现
from random import shuffle
"""归并排序"""
# 将一列无序的数按从小到大的顺序进行排列
def merge_sort(num_lsit1:list,num_list2:list):
i = j = 0
result = []
while 1:
# 如果第一个列表的元素全部加入结果,将第二个列表的元素全部加入结果,排序结束
if i == len(num_lsit1):
result.extend(num_list2[j:])
return result
# 如果第二个列表的元素全部加入结果,将第一个列表的元素全部加入结果,排序结束
elif j == len(num_list2):
result.extend(num_lsit1[i:])
return result
# 比对当前要比较的两个元素,将较小的加入结果,并将相应的索引往后移一位
if num_lsit1[i] < num_list2[j]:
result.append(num_lsit1[i])
i += 1
else:
result.append(num_list2[j])
j += 1
def merge(num_list):
if len(num_list) == 1:
return num_list
left = merge(num_list[:len(num_list)//2])
right = merge(num_list[len(num_list)//2:])
return merge_sort(left, right)
num_list_demo1 = [x for x in range(100)]
shuffle(num_list_demo1)
print("排序前:", num_list_demo1)
print("排序后:", merge(num_list_demo1))
