熱線電話：13121318867

登錄
首頁精彩閱讀python實現折半查找和歸并排序算法
python實現折半查找和歸并排序算法
2018-05-03
收藏

python實現折半查找和歸并排序算法

今天依舊是學算法，前幾天在搞bbs項目，界面也很丑，評論功能好像也有BUG?，F在不搞了，得學下算法和數據結構，筆試過不了，連面試的機會都沒有……

今天學了折半查找算法，折半查找是蠻簡單的，但是歸并排序我就挺懵比，看教材C語言寫的歸并排序看不懂，后來參考了別人的博客，終于搞懂了。

折半查找

先看下課本對于 折半查找的講解。注意了，折半查找是對于有序序列而言的。每次折半，則查找區間大約縮小一半。low,high分別為查找區間的第一個下標與最后一個下標。出現low>high時，說明目標關鍵字在整個有序序列中不存在，查找失敗。

看我用python編程實現:


defBinSearch(array, key, low, high):
 mid=int((low+high)/2)
 ifkey==array[mid]:# 若找到
  returnarray[mid]
 iflow > high:
  returnFalse
 
 ifkey < array[mid]:
  returnBinSearch(array, key, low, mid-1)#遞歸
 ifkey > array[mid]:
  returnBinSearch(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)# 通過折半查找，找到65
 print(ret)

輸出: 在列表中查找76.

76

時間復雜度：O(logn)

歸并排序算法

先闡述一下排序思路：

首先歸并排序使用了二分法，歸根到底的思想還是分而治之。歸并排序是指把無序的待排序序列分解成若干個有序子序列，并把有序子序列合并為整體有序序列的過程。長度為1的序列是有序的。因此當分解得到的子序列長度大于1時，應繼續分解，直到長度為1.

(下圖是分解過程，圖自python編程實現歸并排序)

合并的過程如下:

很好，你現在可以和別人說，老子會歸并排序了。但是讓你寫代碼出來，相信你是不會的……

來來來，看我用python寫的歸并排序算法:

defmerge_sort(array):# 遞歸分解
 mid=int((len(array)+1)/2)
 iflen(array)==1:# 遞歸結束的條件，分解到列表只有一個數據時結束
  returnarray
 list_left=merge_sort(array[:mid])
 list_right=merge_sort(array[mid:])
 print(">>>list_left:", list_left)
 print(">>>list_right:", list_right)
 returnmerge(list_left, list_right)# 進行歸并
 
 
defmerge(list_left, list_right):# 進行歸并
 final=[]
 whilelist_leftandlist_right:
  iflist_left[0] <=list_right[0]:# 如果將"<="改為"<",則歸并排序不穩定
   final.append(list_left.pop(0))
  else:
   final.append(list_right.pop(0))
 
 returnfinal+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] 

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

空間復雜度:O(n)

穩定性:穩定

對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行歸并排序的實例如下:

使用歸并排序為一列數字進行排序的宏觀過程:

以上就是本文的全部內容，希望對大家的學習有所幫助



CDA數據分析師考試相關入口一覽（建議收藏）：

? 想報名CDA認證考試，點擊>>>   “CDA報名” 了解CDA考試詳情；

? 想學習CDA考試教材，點擊>>> “CDA教材” 了解CDA考試詳情；

? 想加入CDA考試題庫，點擊>>> “CDA題庫” 了解CDA考試詳情；

? 想了解CDA考試含金量，點擊>>> “CDA含金量” 了解CDA考試詳情；

python

數據分析咨詢請掃描二維碼

若不方便掃碼，搜微信號：CDAshujufenxi

上一篇淺析大數據隱私問題
下一篇越來越多Java程序員轉行大數據的原因
數據分析師考試動態
CDA報考指南
數據分析學習
數據分析師資訊
更多

CDA教育閉環

常見問題

關于我們

CDA數據分析師公眾號

  • CDA數據分析師公眾號

CDA考試中心小程序

  • CDA考試中心服務號

CDA數據分析師App下載

  • CDA數據分析師App下載
Copyright © 2015-2021, www.ruiqisteel.com All Rights Reserved. CDA數據分析師(北京國富如荷網絡科技有限公司) 版權所有 京ICP備11001960號-9 京公網安備 11010802034615號 經營許可證編號：京B2-20210330
聯系電話：13321103290 (微信同號)

OK
客服在線
立即咨詢
日韩人妻系列无码专区视频,先锋高清无码,无码免费视欧非,国精产品一区一区三区无码
客服在線
立即咨詢