快捷導(dǎo)航

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

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

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

0、前言

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

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

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

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

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

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

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

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

2、算法過(guò)程圖解

3、代碼實(shí)現(xiàn)

代碼如下（示例01）：

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

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

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

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

 # 遞歸調(diào)用，無(wú)限切割下去
 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)去，對(duì)應(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
 # 下面的這兩個(gè)就是，如果有一個(gè)列表全部添加了，另外一個(gè)列表直接添加到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}')

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

4、評(píng)判算法

最好時(shí)間復(fù)雜度：O(n log n)
最壞時(shí)間復(fù)雜度：O(n log n)
平均時(shí)間復(fù)雜度：O(n log n)
空間復(fù)雜度：O(n)
算法穩(wěn)定性：穩(wěn)定的排序

總結(jié)

到此這篇關(guān)于python基本算法之實(shí)現(xiàn)歸并排序(Merge sort)的文章就介紹到這了,更多相關(guān)python歸并排序(Merge sort)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: