欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

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

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)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Django實(shí)現(xià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的終極解決方法

    這篇文章主要介紹了詳解Pycharm出現(xiàn)out of memory的終極解決方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-03-03
  • python 將html轉(zhuǎn)換為pdf的幾種方法

    python 將html轉(zhuǎn)換為pdf的幾種方法

    這篇文章主要介紹了python 將html轉(zhuǎn)換為pdf的幾種方法,幫助大家更好的理解和使用python,感興趣的朋友可以了解下
    2020-12-12
  • python常用函數(shù)與用法示例

    python常用函數(shù)與用法示例

    這篇文章主要介紹了python常用函數(shù)與用法,涉及Python文件讀取、刪除、數(shù)值計(jì)算、打印等相關(guān)操作技巧,需要的朋友可以參考下
    2019-07-07
  • python+mysql實(shí)現(xiàn)教務(wù)管理系統(tǒng)

    python+mysql實(shí)現(xiàn)教務(wù)管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了python+mysql實(shí)現(xiàn)教務(wù)管理系統(tǒng),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-02-02
  • python交互式圖形編程實(shí)例(一)

    python交互式圖形編程實(shí)例(一)

    這篇文章主要為大家詳細(xì)介紹了python交互式圖形編程實(shí)例,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-11-11
  • Python用matplotlib庫畫圖中文和負(fù)號顯示為方框的問題解決

    Python用matplotlib庫畫圖中文和負(fù)號顯示為方框的問題解決

    matplotlib中畫圖的時(shí)候會遇到負(fù)號顯示為方框的問題,下面這篇文章主要給大家介紹了關(guān)于Python用matplotlib庫畫圖中文和負(fù)號顯示為方框的問題解決,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-07-07
  • python如何修改文件時(shí)間屬性

    python如何修改文件時(shí)間屬性

    這篇文章主要介紹了python修改文件時(shí)間屬性的方法,幫助大家更好的理解和使用python,感興趣的朋友可以了解下
    2021-02-02
  • Python爬蟲谷歌Chrome F12抓包過程原理解析

    Python爬蟲谷歌Chrome F12抓包過程原理解析

    這篇文章主要介紹了Python爬蟲谷歌Chrome F12抓包過程原理解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-06-06
  • 使用Python創(chuàng)建一個(gè)視頻管理器并實(shí)現(xiàn)視頻截圖功能

    使用Python創(chuàng)建一個(gè)視頻管理器并實(shí)現(xiàn)視頻截圖功能

    在這篇博客中,我將向大家展示如何使用 wxPython 創(chuàng)建一個(gè)簡單的圖形用戶界面 (GUI) 應(yīng)用程序,該應(yīng)用程序可以管理視頻文件列表、播放視頻,并生成視頻截圖,我們將逐步實(shí)現(xiàn)這些功能,并確保代碼易于理解和擴(kuò)展,感興趣的小伙伴跟著小編一起來看看吧
    2024-08-08

最新評論