pythonå®ç°æåæ¥æ¾åå½å¹¶æåºç®æ³
ä»å¤©ä¾æ§æ¯å¦ç®æ³ï¼åå 天å¨æbbs项ç®ï¼çé¢ä¹å¾ä¸ï¼è¯è®ºåè½å¥½åä¹æBUGãç°å¨ä¸æäºï¼å¾å¦ä¸ç®æ³åæ°æ®ç»æï¼ç¬è¯è¿ä¸äºï¼è¿é¢è¯çæºä¼é½æ²¡æâ¦â¦
ä»å¤©å¦äºæåæ¥æ¾ç®æ³ï¼æåæ¥æ¾æ¯è®ç®åçï¼ä½æ¯å½å¹¶æåºæå°±æºæµæ¯ï¼çææ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 }è¿è¡å½å¹¶æåºçå®ä¾å¦ä¸:
使ç¨å½å¹¶æåºä¸ºä¸åæ°åè¿è¡æåºçå®è§è¿ç¨:
以ä¸å°±æ¯æ¬æçå
¨é¨å
容ï¼å¸æ对大家çå¦ä¹ ææ帮å©
温馨提示:答案为网友推荐,仅供参考