国产成人精品久久免费动漫-国产成人精品天堂-国产成人精品区在线观看-国产成人精品日本-a级毛片无码免费真人-a级毛片毛片免费观看久潮喷

您的位置:首頁技術文章
文章詳情頁

Python查找算法之分塊查找算法的實現

瀏覽:3日期:2022-06-23 08:59:52
一、分塊查找算法

分塊查找是二分法查找和順序查找的改進方法,分塊查找要求索引表是有序的,對塊內結點沒有排序要求,塊內結點可以是有序的也可以是無序的。

分塊查找就是把一個大的線性表分解成若干塊,每塊中的節(jié)點可以任意存放,但塊與塊之間必須排序。與此同時,還要建立一個索引表,把每塊中的最大值作為索引表的索引值,此索引表需要按塊的順序存放到一個輔助數組中。查找時,首先在索引表中進行查找,確定要找的結點所在的塊。由于索引表是排序的,因此,對索引表的查找可以采用順序查找或二分查找;然后,在相應的塊中采用順序查找,即可找到對應的結點。

例如,有這樣一列數據:23、43、56、78、97、100、120、135、147、150。如下圖所示:

Python查找算法之分塊查找算法的實現

想要查找的數據是 150,使用分塊查找法步驟如下:

步驟1:將上圖所示的數據進行分塊,按照每塊長度為 4 進行分塊,分塊情況如下圖所示:

Python查找算法之分塊查找算法的實現

說明:每塊的長度是任意指定的,博主在這里用的長度為4,讀者可以根據自己的需要指定每塊長度。

步驟2:選取各塊中的最大關鍵字構成一個索引表,即選取上圖所示的各塊的最大值,第一塊最大的值是 78,第二塊最大的值是 135,第三塊最大值是 155,形成的索引表如下圖所示:

Python查找算法之分塊查找算法的實現

步驟3:用順序查找或者二分查找判斷想要查找數據 150 在上圖所示的索引表中的哪塊內容中,這里博主用的是二分查找法,即先取中間值 135 與 150 比較,如下圖所示:

Python查找算法之分塊查找算法的實現

步驟4:結果是中間位置的數據 135 比目標數據 150 小,因此目標數據在 135 的下一塊內。將數據定位在第 3 塊內,此時將第 3 塊內的數據取出,進行順序比較,如下圖所示:

Python查找算法之分塊查找算法的實現

步驟5:通過順序查找第 3 塊的內容,終于在第 9 個位置找到目標數,此時分塊查找結束。

總結:至此,分塊查找算法已經講解完畢。通過和二分查找法和順序查找法對比來看,分塊查找的速度雖然不如二分查找算法,但比順序查找算法快得多。當數據很多且塊數很大時,對索引表可以采用二分查找,這樣能夠進一步提高查找的速度。

二、實例:實現分塊查找算法

具體代碼如下:

def search(data, key): # 用二分查找 想要查找的數據在哪塊內 length = len(data) # 數據列表長度 first = 0 # 第一位數位置 last = length - 1 # 最后一個數據位置 print(f'長度:{length} 分塊的數據是:{data}') # 輸出分塊情況 while first <= last:mid = (last + first) // 2 # 取中間位置if data[mid] > key: # 中間數據大于想要查的數據 last = mid - 1 # 將last的位置移到中間位置的前一位elif data[mid] < key: # 中間數據小于想要查的數據 first = mid + 1 # 將first的位置移到中間位置的后一位else: return mid # 返回中間位置 return False# 分塊查找def block(data, count, key): # 分塊查找數據,data是列表,count是每塊的長度,key是想要查找的數據 length = len(data) # 表示數據列表的長度 block_length = length // count # 一共分的幾塊 if count * block_length != length: # 每塊長度乘以分塊總數不等于數據總長度block_length += 1 # 塊數加1 print('一共分', block_length, '塊') # 塊的多少 print('分塊情況如下:') for block_i in range(block_length): # 遍歷每塊數據block_data = [] # 每塊數據初始化for i in range(count): # 遍歷每塊數據的位置 if block_i * count + i >= length: # 每塊長度要與數據長度比較,一旦大于數據長度break # 就退出循環(huán) block_data.append(data[block_i * count + i]) # 每塊長度要累加上一塊的長度result = search(block_data, key) # 調用二分查找的值if result != False: # 查找的結果不為False return block_i * count + result # 就返回塊中的索引位置 return Falsedata = [23, 43, 56, 78, 97, 100, 120, 135, 147, 150, 155] # 數據列表result = block(data, 4, 150) # 第二個參數是塊的長度,最后一個參數是要查找的元素print('查找的值得索引位置是:', result) # 輸出結果

運行結果如下圖所示:

Python查找算法之分塊查找算法的實現

從上面的運行結果看到,當查找 150 時,查找結果完全符合上述描述的步驟。

到此這篇關于Python查找算法之分塊查找算法的實現的文章就介紹到這了,更多相關Python 分塊查找算法內容請搜索好吧啦網以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持好吧啦網!

標簽: Python 編程
相關文章:
主站蜘蛛池模板: 日本一道免费一区二区三区 | 国产成人免费在线观看 | 91无套极品外围在线播放 | 亚洲国产成人在线观看 | 亚洲九九视频 | 免费a级毛片视频 | 亚洲在线欧美 | 国产亚洲精品一区二区在线播放 | 久久久久性| 91精品免费看 | 国产女乱淫真高清免费视频 | 色老久久精品偷偷鲁一区 | 久草免费资源在线 | 手机在线观看毛片 | 日韩精品一区二区三区乱码 | 亚洲一区2区三区4区5区 | 亚洲国产韩国一区二区 | 欧美人成在线观看ccc36 | 男女男精品视频在线播放 | 国产精品露脸脏话对白 | 精品国产美女福到在线不卡f | 国产午夜在线观看视频播放 | 国产成人毛片精品不卡在线 | 国产免费爽爽视频免费可以看 | 欧美一级免费观看 | 日本一区二区三区高清在线观看 | 中文字幕视频在线观看 | a欧美在线 | 天干天干天啪啪夜爽爽色 | 美女舒服好紧太爽了视频 | 国产精品国产亚洲精品看不卡 | 成人亚州 | 成年人黄色免费网站 | 亚洲第一网站在线观看 | 欧美在线bdsm调教一区 | 久久香蕉国产线看观看式 | av18在线播放 | 亚洲 欧美 日韩中文字幕一区二区 | 天堂免费在线视频 | 在线a人片免费观看国产 | 手机看片免费基地 |