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))