python歸并排序算法怎么實(shí)現(xiàn)

歸并排序是一種分治算法，它將一個(gè)大的問(wèn)題分解為多個(gè)小問(wèn)題，然后將小問(wèn)題的解合并起來(lái)得到最終的解。

歸并排序的實(shí)現(xiàn)步驟如下：

1. 將待排序的列表遞歸地分成兩個(gè)子列表，直到每個(gè)子列表只有一個(gè)元素為止。
2. 對(duì)每個(gè)子列表進(jìn)行歸并排序，即不斷地將兩個(gè)已排序的子列表合并成一個(gè)有序的子列表。
3. 將兩個(gè)有序的子列表合并成一個(gè)有序的列表。

下面是一個(gè)基于遞歸的歸并排序算法的示例代碼：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 將列表分成兩個(gè)子列表
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # 遞歸地對(duì)子列表進(jìn)行歸并排序
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 合并兩個(gè)有序的子列表
    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0
    
    # 從兩個(gè)子列表中按順序選取較小的元素放入 merged 列表中
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    
    # 將剩余的元素放入 merged 列表中
    merged += left[i:]
    merged += right[j:]
    
    return merged

使用這個(gè)算法來(lái)排序一個(gè)列表的示例代碼如下：

arr = [54, 26, 93, 17, 77, 31, 44, 55, 20]
sorted_arr = merge_sort(arr)
print(sorted_arr)

輸出結(jié)果為：[17, 20, 26, 31, 44, 54, 55, 77, 93]