BFPTR算法

来自于Blum、Floyd、Pratt、Rivest、Tarjan这5个人，一起发布了一篇名为 “Time bounds for selection” 的论文，有兴趣可以看一下:/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