python基本算法之實(shí)現(xiàn)歸并排序(Merge sort)
0、前言
評判一個(gè)算法的好壞的標(biāo)準(zhǔn):
- 時(shí)間復(fù)雜度
- 空間復(fù)雜度
1、歸并排序算法是什么?
冒泡排序(Bubble Sort)是一種建立在歸并操作上面的一種有效的排序算法,由John von neumann于1945年發(fā)明。采用分治法(Divide and Conquer)的經(jīng)典應(yīng)用??!將規(guī)模較大的排序問題化歸到較小的規(guī)模上解決。
基本實(shí)現(xiàn)包含下面的兩種方法:
自上而下的遞歸
自下而上的迭代
將已經(jīng)有的有序子序列合并,得到完全有序的子序列。就是先得到每個(gè)子序列有序,然后在使得兩個(gè)子序列合并成為一個(gè)有序的。如果是把兩個(gè)有序表合并成為一個(gè)有序表,成為二路歸并。
歸并排序的性能不受到輸入數(shù)據(jù)的影響,這一個(gè)和選擇排序是一樣的,但是性能比選擇排序要好,性能始終是O(n log n)。但是性能的優(yōu)越必定是額外的內(nèi)存空間作為巨大代價(jià)的!
2、算法過程圖解
3、代碼實(shí)現(xiàn)
代碼如下(示例01):
""" Merge_Sort 歸并排序 分治算法Divide and Conquer 時(shí)間復(fù)雜度: """ # 切割數(shù)組 的函數(shù) def merge_sort(alist): # 如果長度小于等于1 ,不能再分割了 if len(alist) <= 1: return alist # 根據(jù)列表長度確定拆分的中間位置 mid_index = len(alist)//2 # 使用切片實(shí)現(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 # 下面的這兩個(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)行,看一哈具體的過程,結(jié)合動(dòng)態(tài)圖片演示理解更好!
4、評判算法
- 最好時(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- DataFrame 數(shù)據(jù)合并實(shí)現(xiàn)(merge,join,concat)
- Python自定義聚合函數(shù)merge與transform區(qū)別詳解
- 淺談keras中的Merge層(實(shí)現(xiàn)層的相加、相減、相乘實(shí)例)
- 詳解Python3 pandas.merge用法
- 詳解PANDAS 數(shù)據(jù)合并與重塑(join/merge篇)
- pandas dataframe的合并實(shí)現(xiàn)(append, merge, concat)
- 在Pandas中DataFrame數(shù)據(jù)合并,連接(concat,merge,join)的實(shí)例
- Python Merge函數(shù)原理及用法解析
相關(guān)文章
Django實(shí)現(xiàn)簡單分頁功能的方法詳解
這篇文章主要介紹了Django實(shí)現(xiàn)簡單分頁功能的方法,結(jié)合實(shí)例形式分析了django的第三方模塊django-pure-pagination的安裝、使用及實(shí)現(xiàn)分頁的相關(guān)操作技巧,需要的朋友可以參考下2017-12-12詳解Pycharm出現(xiàn)out of memory的終極解決方法
這篇文章主要介紹了詳解Pycharm出現(xiàn)out of memory的終極解決方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03python 將html轉(zhuǎn)換為pdf的幾種方法
這篇文章主要介紹了python 將html轉(zhuǎn)換為pdf的幾種方法,幫助大家更好的理解和使用python,感興趣的朋友可以了解下2020-12-12python+mysql實(shí)現(xiàn)教務(wù)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了python+mysql實(shí)現(xiàn)教務(wù)管理系統(tǒng),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-02-02Python用matplotlib庫畫圖中文和負(fù)號顯示為方框的問題解決
matplotlib中畫圖的時(shí)候會遇到負(fù)號顯示為方框的問題,下面這篇文章主要給大家介紹了關(guān)于Python用matplotlib庫畫圖中文和負(fù)號顯示為方框的問題解決,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-07-07使用Python創(chuàng)建一個(gè)視頻管理器并實(shí)現(xiàn)視頻截圖功能
在這篇博客中,我將向大家展示如何使用 wxPython 創(chuàng)建一個(gè)簡單的圖形用戶界面 (GUI) 應(yīng)用程序,該應(yīng)用程序可以管理視頻文件列表、播放視頻,并生成視頻截圖,我們將逐步實(shí)現(xiàn)這些功能,并確保代碼易于理解和擴(kuò)展,感興趣的小伙伴跟著小編一起來看看吧2024-08-08