0、前言

評判一個算法的好壞的標準：

時間復雜度

空間復雜度

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

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

基本實現包含下面的兩種方法：

自上而下的遞歸

自下而上的迭代

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

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

2、算法過程圖解

3、代碼實現

代碼如下(示例01)：

"""

Merge_Sort 歸并排序

分治算法Divide and Conquer

時間復雜度：

"""

# 切割數組 的函數

def merge_sort(alist):

# 如果長度小于等于1 ，不能再分割了

if len(alist) <= 1:

return alist

# 根據列表長度確定拆分的中間位置

mid_index = len(alist)//2

# 使用切片實現對列表的切分

# left_list = alist[:mid_index]

# right_list = alist[mid_index:]

# 遞歸調用，無限切割下去

left_list = merge_sort(alist[:mid_index])

right_list = merge_sort(alist[mid_index:])

return merge(left_list, right_list)

# 排序的函數

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):

# 哪邊的元素小于另外一邊的的元素就把哪邊的元素加入進去，對應的索引加一

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運行，看一哈具體的過程，結合動態圖片演示理解更好！

4、評判算法

最好時間復雜度：O(n log n)

最壞時間復雜度：O(n log n)

平均時間復雜度：O(n log n)

空間復雜度：O(n)

算法穩定性：穩定的排序

總結

到此這篇關于python基本算法之實現歸并排序(Merge sort)的文章就介紹到這了,更多相關python歸并排序(Merge sort)內容請搜索隨便開發網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持隨便開發網！

總結

以上是生活随笔為你收集整理的python 归并排序算法_python基本算法之实现归并排序(Merge sort)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。