python實(shí)現(xiàn)折半查找和歸并排序算法
今天依舊是學(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)文章
pytorch中dataloader 的sampler 參數(shù)詳解
這篇文章主要介紹了pytorch中dataloader 的sampler 參數(shù)詳解,文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,感興趣的小伙伴可以參考一下2022-09-09python 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-07python數(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