BFPTR算法

來自于Blum、Floyd、Pratt、Rivest、Tarjan這5個人，一起發布了一篇名為 “Time bounds for selection” 的論文，有興趣可以看一下:https://pan.baidu.com/s/1QEWjZBrjEJ7zTIrI99sFYA。

下面是一種實現方式，這種有一個問題，只是找到中位數了，標號還要搜索然后此時的數組是有結構規律的，劃分數組的時候使用的是快排的劃分，沒有用到這里insert_sort排序產生的局部有序的特征，改進優化方法：在找中位數組中位數的過程中想辦法記錄下來，哪些數據必定小于中位數的在左上方，那些數據必定大于中位數在右下方， 以及不確定的那一塊。

# -*- coding: utf-8 -*-# 簡單的插入排序 def insert_sort(arr,low,high):# 指針i,代表第幾次插入，第0次，就默認首元素放入有序列表# 從第1次開始，拿一個元素放入有序列表，或者理解為拿原數組里面# 第i個元素放入有序數組，在這里是原地操作的，要么使用交換，要么# 先拿出一個元素在空中，數組里面就流出了一個空位for i in range(low+1,high+1):# 把第i個元素拿起，暫時放在空中temp = arr[i]# 指針j是從尾部掃描已排列的有序數組，注意有序列表是從小到大排列的# j一直都是指在空閑的位置的j = i# 遇到比空中的元素大的元素，大的元素后移一位，移到空出來的那個位置# 此時就又空出來一個位置，更新空閑的位置j,...直到碰到比空中的元素小的元素# 空中元素的位置就找到了，就是現在j指的空閑位置while arr[j-1] > temp and j >low:arr[j] = arr[j-1]j -=1# 把空中元素放入空閑位置arr[j] = temp# 這個一個可以準確找到中位數的算法？顯然不是的這個只是大概找中位數的方法，而且還有一個 # 致命的問題，只是找到中位數了，標號還要搜索 # 然后此時的數組是有結構規律的，劃分數組的時候使用的是快排的劃分，沒有用到這里面 # insert_sort排序產生的局部有序的特征，改進優化方法：在找中位數組中位數的過程中 # 想辦法記錄下來，哪些數據必定小于中位數的在左上方，那些數據必定大于中位數在右下方， # 以及不確定的那一塊 def findMid(arr,low,high): ############################################################################### # Divide ############################################################################### # 這里的兩個指針為每個小分組的頭和尾，也可以只用一個指針left = lowright = low+4# count指的是中位數數組的指針count = 0# 當小數組的尾指針小于等于右邊界限時，對每個小組排序，得到每個小組的中位數while right <= high:insert_sort(arr,left,right)# 因為中位數是分散的步長為5，對于我來說不好處理，所以此時處理時把中位都放在數組的# 前面，這樣下一輪時就比較好處理了，但是這樣處理，就破壞了數組有序的規律，讓最后# 無法利用數組的有序規律來劃分數據，這里可以優化arr[low + count],arr[left +2] = arr[left +2],arr[low + count]# 處理下一組left +=5right +=5# 記得更新中位數數組的指針count +=1# 當跳出循壞時，就需要處理余數，或者沒有進入循環，也要處理余數# 把余數排序，獲取中位數，加入到中位數列表if left <=high:insert_sort(arr,left,high)arr[low + count],arr[left+(high-left)//2] = arr[left+(high-left)//2],arr[low + count]count +=1# 以上過程是這個問題劃分子問題的過程，也就是partion的過程，也就是把問題規模n變成# n//5的過程。 ############################################################################### # Conquer ################################################################################獲取到中位數數組，得到了子問題，下面就考慮治conquer了# 第一種情況，數組沒有經過5分組，排序后直接到這里，直接返回在首位的中位數，這種情況下count=1# 當進入了5分組沒有進入余數處理，這時count=1，也應該是返回首元素# 其他情況count>=0時，這兩個元素還沒有排序，所以要進入下一輪排序一下，變成count=1輸出首元素# count就是low>high的情況，直接返回空if count ==0:returnif count ==1:return arr[low]else:# 注意count是指中位數元素的數量，對應數組上的指針需要-1return findMid(arr,low,low+count-1)#標號需要通過檢索得到 def findIndex(arr,mid):for i in range(len(arr)):if arr[i] == mid:return idef partion_with_index(arr,low,high,index):def partition(arr,low,high):# 這時另外一種考慮方式，而且他是不需要額外空間的，他只使用一個指針來區分小于基準和大于基準的# pointer_less_than代表這個指針的左邊全部都是小于基準的（包括自己，不包括首元素）# 然后從左往右掃描，遇到小于基準的元素，就把小于基準元素區域的后面緊接著的一個元素和他交換# 那么小于基準元素區域就多了一個元素，。。。就這樣小于基準的元素就連在了一起# 首元素是基準元素，小于基準元素區域塊，大于基準元素區域塊，現在分成了三個部分# 把首元素和小于基準元素區域塊最后一個元素交換，那三部分就變成，小于的，基準，大于的# 剛開始小于基準的元素為0，暫且指向首位值pointer_less_than = low# 然后一次掃描后面所有元素for i in range(pointer_less_than +1,high+1):# 遇到小于基準的，就把小于基準元素區域的后面緊接著的一個元素和他交換，小于的塊相當于也更新了if arr[i] < arr[low] :pointer_less_than +=1arr[pointer_less_than],arr[i]=arr[i],arr[pointer_less_than]# 把首元素和小于基準元素區域塊最后一個元素交換，那三部分就變成，小于的，基準，大于的 arr[low],arr[pointer_less_than] = arr[pointer_less_than],arr[low]return pointer_less_thanarr[low],arr[index] = arr[index],arr[low]return partition(arr,low,high)def BFPTR(arr,low,high,k): ######################################################################### divide ######################################################################### 首先獲取midmid = findMid(arr,low,high)# 獲取此時mid的indexmid_index = findIndex(arr,mid)# 根據mid來劃分數據，返回的是中間的index（就是排序后最終的位置）index =partion_with_index(arr,low,high,mid_index) ######################################################################## Conquer ######################################################################## #根據index做出子問題的處理if index == k:return arr[index]elif index > k:return BFPTR(arr,low,index-1,k)else:return BFPTR(arr,index+1,high,k)arr3 = [7,3,66,33,22,66,9,0,1,11,14,17,9,10,13,99,44,33,77,88,99,101,404,87,44,22,11,99,43,22] print(sorted(arr3)) print(BFPTR(arr3,0,len(arr3)-1,(len(arr3)-1)//2-1)) runfile('D:/share/test/BFPTR.py', wdir='D:/share/test') [0, 1, 3, 7, 9, 9, 10, 11, 11, 13, 14, 17, 22, 22, 22, 33, 33, 43, 44, 44, 66, 66, 77, 87, 88, 99, 99, 99, 101, 404] 22 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的分治法：BFPTR算法找第k小的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。