快捷導(dǎo)航

python基本算法之實現(xiàn)歸并排序(Merge sort)

更新時間：2020年09月01日 16:02:02 作者：海歌同學(xué)

這篇文章主要給大家介紹了關(guān)于python基本算法之實現(xiàn)歸并排序(Merge sort)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

0、前言

評判一個算法的好壞的標(biāo)準(zhǔn)：

時間復(fù)雜度
空間復(fù)雜度

1、歸并排序算法是什么？

冒泡排序(Bubble Sort)是一種建立在歸并操作上面的一種有效的排序算法，由John von neumann于1945年發(fā)明。采用分治法（Divide and Conquer）的經(jīng)典應(yīng)用?。⒁?guī)模較大的排序問題化歸到較小的規(guī)模上解決。

基本實現(xiàn)包含下面的兩種方法：

自上而下的遞歸
自下而上的迭代

將已經(jīng)有的有序子序列合并，得到完全有序的子序列。就是先得到每個子序列有序，然后在使得兩個子序列合并成為一個有序的。如果是把兩個有序表合并成為一個有序表，成為二路歸并。

歸并排序的性能不受到輸入數(shù)據(jù)的影響，這一個和選擇排序是一樣的，但是性能比選擇排序要好，性能始終是O(n log n）。但是性能的優(yōu)越必定是額外的內(nèi)存空間作為巨大代價的！

2、算法過程圖解

3、代碼實現(xiàn)

代碼如下（示例01）：

"""
Merge_Sort 歸并排序
分治算法Divide and Conquer
時間復(fù)雜度：
"""

# 切割數(shù)組 的函數(shù)
def merge_sort(alist):
 # 如果長度小于等于1 ，不能再分割了
 if len(alist) <= 1:
  return alist

 # 根據(jù)列表長度確定拆分的中間位置
 mid_index = len(alist)//2

 # 使用切片實現(xiàn)對列表的切分
 # left_list = alist[:mid_index]
 # right_list = alist[mid_index:]

 # 遞歸調(diào)用，無限切割下去
 left_list = merge_sort(alist[:mid_index])
 right_list = merge_sort(alist[mid_index:])
 return merge(left_list, right_list)

# 排序的函數(shù)
def merge(left_list, right_list):
 l_index,r_index = 0,0
 merge_list = []
 # 判斷列表里面是否還有元素可以用
 while l_index < len(left_list) and r_index < len(right_list):
  # 哪邊的元素小于另外一邊的的元素就把哪邊的元素加入進(jìn)去，對應(yīng)的索引加一
  if left_list[l_index] < right_list[r_index]:
   merge_list.append(left_list[l_index])
   l_index += 1
  else:
   merge_list.append(right_list[r_index])
   r_index += 1
 # 下面的這兩個就是，如果有一個列表全部添加了，另外一個列表直接添加到merge_list里面了
 merge_list += left_list[l_index:]
 merge_list += right_list[r_index:]
 return merge_list

if __name__ == '__main__':
 alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
 print(f'原列表的順序：{alist}')
 alist = merge_sort(alist)
 print(f'選擇排序之后的列表的順序：{alist}')

里面的左右列表都是被劃分到了只有一個元素的是去比較和添加的。大家可以把代碼放置到編譯器里面，debug運行，看一哈具體的過程，結(jié)合動態(tài)圖片演示理解更好！

4、評判算法