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

python實(shí)現(xiàn)折半查找和歸并排序算法

 更新時(shí)間:2017年04月14日 09:01:02   作者:前程明亮  
這篇文章主要介紹了python實(shí)現(xiàn)折半查找和歸并排序算法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

今天依舊是學(xué)算法,前幾天在搞bbs項(xiàng)目,界面也很丑,評(píng)論功能好像也有BUG?,F(xiàn)在不搞了,得學(xué)下算法和數(shù)據(jù)結(jié)構(gòu),筆試過(guò)不了,連面試的機(jī)會(huì)都沒(méi)有……

今天學(xué)了折半查找算法,折半查找是蠻簡(jiǎn)單的,但是歸并排序我就挺懵比,看教材C語(yǔ)言寫(xiě)的歸并排序看不懂,后來(lái)參考了別人的博客,終于搞懂了。

折半查找

先看下課本對(duì)于 折半查找的講解。注意了,折半查找是對(duì)于有序序列而言的。每次折半,則查找區(qū)間大約縮小一半。low,high分別為查找區(qū)間的第一個(gè)下標(biāo)與最后一個(gè)下標(biāo)。出現(xiàn)low>high時(shí),說(shuō)明目標(biāo)關(guān)鍵字在整個(gè)有序序列中不存在,查找失敗。

看我用python編程實(shí)現(xiàn):

def BinSearch(array, key, low, high):
 mid = int((low+high)/2)
 if key == array[mid]: # 若找到
  return array[mid]
 if low > high:
  return False

 if key < array[mid]:
  return BinSearch(array, key, low, mid-1) #遞歸
 if key > array[mid]:
  return BinSearch(array, key, mid+1, high)



if __name__ == "__main__":
 array = [4, 13, 27, 38, 49, 49, 55, 65, 76, 97]
 ret = BinSearch(array, 76, 0, len(array)-1) # 通過(guò)折半查找,找到65
 print(ret)

輸出: 在列表中查找76.

76

時(shí)間復(fù)雜度:O(logn)

歸并排序算法

先闡述一下排序思路:

首先歸并排序使用了二分法,歸根到底的思想還是分而治之。歸并排序是指把無(wú)序的待排序序列分解成若干個(gè)有序子序列,并把有序子序列合并為整體有序序列的過(guò)程。長(zhǎng)度為1的序列是有序的。因此當(dāng)分解得到的子序列長(zhǎng)度大于1時(shí),應(yīng)繼續(xù)分解,直到長(zhǎng)度為1.

(下圖是分解過(guò)程,圖自python編程實(shí)現(xiàn)歸并排序)

合并的過(guò)程如下:

很好,你現(xiàn)在可以和別人說(shuō),老子會(huì)歸并排序了。但是讓你寫(xiě)代碼出來(lái),相信你是不會(huì)的……

來(lái)來(lái)來(lái),看我用python寫(xiě)的歸并排序算法:

def merge_sort(array): # 遞歸分解
 mid = int((len(array)+1)/2)
 if len(array) == 1: # 遞歸結(jié)束的條件,分解到列表只有一個(gè)數(shù)據(jù)時(shí)結(jié)束
  return array
 list_left = merge_sort(array[:mid])
 list_right = merge_sort(array[mid:])
 print(">>>list_left:", list_left)
 print(">>>list_right:", list_right)
 return merge(list_left, list_right) # 進(jìn)行歸并


def merge(list_left, list_right): # 進(jìn)行歸并
 final = []
 while list_left and list_right:
  if list_left[0] <= list_right[0]: # 如果將"<="改為"<",則歸并排序不穩(wěn)定
   final.append(list_left.pop(0))
  else:
   final.append(list_right.pop(0))

 return final+list_left+list_right # 返回排序好的列表


if __name__=="__main__":
 array = [49, 38, 65, 97, 76]
 print(merge_sort(array))輸出:

輸出:

>>>list_left: [49]
>>>list_right: [38]
>>>list_left: [38, 49]
>>>list_right: [65]
>>>list_left: [97]
>>>list_right: [76]
>>>list_left: [38, 49, 65]
>>>list_right: [76, 97]
[38, 49, 65, 76, 97] 

時(shí)間度雜度: 平均情況=最好情況=最壞情況=O(nlogn)

空間復(fù)雜度: O(n)

穩(wěn)定性: 穩(wěn)定

對(duì)序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進(jìn)行歸并排序的實(shí)例如下:

 使用歸并排序?yàn)橐涣袛?shù)字進(jìn)行排序的宏觀過(guò)程:

以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • Python工程師必考的6個(gè)經(jīng)典面試題

    Python工程師必考的6個(gè)經(jīng)典面試題

    在本篇文章里小編給大家分享的是一篇關(guān)于6個(gè)Python工程師必考的面試題,有需要的朋友們可以參考學(xué)習(xí)下。
    2020-06-06
  • Sublime Text v4.0(4143)安裝方法

    Sublime Text v4.0(4143)安裝方法

    這篇文章主要介紹了Sublime Text v4.0(4143)安裝破解方法,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-02-02
  • Python創(chuàng)建自己的加密貨幣的示例

    Python創(chuàng)建自己的加密貨幣的示例

    這篇文章主要介紹了Python創(chuàng)建自己的加密貨幣的示例,幫助大家更好的理解和學(xué)習(xí)使用python,感興趣的朋友可以了解下
    2021-03-03
  • 詳解Python如何使用Falcon構(gòu)建?API

    詳解Python如何使用Falcon構(gòu)建?API

    Falcon?是一個(gè)Python?的?Web?框架,專(zhuān)注于為構(gòu)建?API?提供一個(gè)極其輕量級(jí)、超全面的性能平臺(tái),下面小編就來(lái)為大家詳細(xì)介紹一下Python如何使用Falcon構(gòu)建?API吧
    2023-11-11
  • 純Python實(shí)現(xiàn)遺傳算法詳解

    純Python實(shí)現(xiàn)遺傳算法詳解

    遺傳算法(GA)是七十年代被霍蘭德提出來(lái)的,那還是8086的時(shí)代,但在如今的3nm時(shí)代,仍然散發(fā)著經(jīng)典的光輝,下面我們就來(lái)看看如何利用Python實(shí)現(xiàn)遺傳算法吧
    2023-08-08
  • 使用Python生成跑馬燈視頻的完整代碼

    使用Python生成跑馬燈視頻的完整代碼

    這篇文章主要介紹了如何使用Python生成跑馬燈視頻,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2023-11-11
  • pytorch中dataloader 的sampler 參數(shù)詳解

    pytorch中dataloader 的sampler 參數(shù)詳解

    這篇文章主要介紹了pytorch中dataloader 的sampler 參數(shù)詳解,文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,感興趣的小伙伴可以參考一下
    2022-09-09
  • python從gbff文件中直接提取cds序列

    python從gbff文件中直接提取cds序列

    這篇文章主要為大家介紹了python從gbff文件中直接提取cds序列示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-07-07
  • python Django的web開(kāi)發(fā)實(shí)例(入門(mén))

    python Django的web開(kāi)發(fā)實(shí)例(入門(mén))

    這篇文章主要介紹了python Django的web開(kāi)發(fā)實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2019-07-07
  • python數(shù)據(jù)結(jié)構(gòu)之圖的實(shí)現(xiàn)方法

    python數(shù)據(jù)結(jié)構(gòu)之圖的實(shí)現(xiàn)方法

    這篇文章主要介紹了python數(shù)據(jù)結(jié)構(gòu)之圖的實(shí)現(xiàn)方法,實(shí)例分析了Python圖的表示方法與常用尋路算法的實(shí)現(xiàn)技巧,需要的朋友可以參考下
    2015-07-07

最新評(píng)論