1.歸并排序介紹
1.歸并排序是采用分治法的一個(gè)非常典型的應(yīng)用吸重。歸并排序的思想就是先遞歸分解數(shù)組阵难，再合并數(shù)組沟沙。
2.將數(shù)組分解最小之后，然后合并兩個(gè)有序數(shù)組，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)其做，誰小就先取誰囱挑，取了后相應(yīng)的指針就往后移一位。
3.然后再比較缠劝，直至一個(gè)數(shù)組為空潮梯，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過來即可。
2. 代碼實(shí)現(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:])
# 將兩個(gè)有序的子序列合并成一個(gè)新的整體
return merge(left_lst,right_lst)
def merge(left_lst, right_lst):
'''合并操作惨恭，將兩個(gè)有序數(shù)組left[]和right[]合并成一個(gè)大的有序數(shù)組'''
#left與right的下標(biāo)指針
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)體之后秉馏，表示左右兩個(gè)列表至少有一個(gè)列表中數(shù)據(jù)全部取完，讓另一個(gè)列表中剩余的元素全部取出來
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)
# 代碼運(yùn)行結(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]
