1.歸并排序介紹

1.歸并排序是采用分治法的一個非常典型的應(yīng)用。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。
2.將數(shù)組分解最小之后，然后合并兩個有序數(shù)組，基本思路是比較兩個數(shù)組的最前面的數(shù)，誰小就先取誰，取了后相應(yīng)的指針就往后移一位。
3.然后再比較，直至一個數(shù)組為空，最后把另一個數(shù)組的剩余部分復(fù)制過來即可。

2. 代碼實現(xiàn)

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):
    '''合并操作，將兩個有序數(shù)組left[]和right[]合并成一個大的有序數(shù)組'''
    #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

    # 退出循環(huán)體之后，表示左右兩個列表至少有一個列表中數(shù)據(jù)全部取完，讓另一個列表中剩余的元素全部取出來
    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)

# 代碼運行結(jié)果
[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]