BFPTR 알고리즘 (서열 중 k 번 째 작은 숫자 구하 기)

1973 년 Blum, Floyd, Pratt, Rivest, Tarjan 과 함께 'Time bounds for selection' 이라는 논문 을 발표 하여 배열 에서 k 대 요소 의 평균 복잡 도 를 O (N) 로 선택 하 는 알고리즘 을 제시 했다. 속칭 '중위 중 자릿수 알고리즘' 이 라 고 한다.
그 사상 은 빠 른 정렬 구분 과정 에 대한 pivot 의 최적화 에 기반 을 두 고 BFPTR 알고리즘 은 5 분 의 중위 수 를 선택 하여 구분 (중위 수의 중위 수 알고리즘) 하 는 것 이다.
프로 세 스:

서열 을 왼쪽 에서 오른쪽으로 5 개 5 개 로 나 누고 요소 의 개수 가 5 보다 작은 그룹 은 한 그룹

이 많 습 니 다.

각 조 를 내림차 순 으로 정렬 (큰 것 에서 작은 것) 하고 각 조 의 중위 수 를 선택 하 며 마지막 조 의 요소 수가 짝수 라면 비교적 큰 요소

를 선택한다.

절차 2 의 중위 수 재 귀 에 대해 절차 1 과 절차 2 를 실시 하고 한 수 만 남 을 때 까지 중심 수

중심 수 를 바탕 으로 서열 을 구분 (parion) 하고 고저 구역 의 판단 을 한 후에 재 귀 여 부 를 결정 한다

.
코드 구현:

#include 
#include 
const int N = 100;
using namespace std;
bool IsBigger(int a, int b)
{
	return a > b;
}
int Find_mid(int a[], int left, int right)           //         
{
	if (left == right)
		return a[left];
	int n = 0;
	int i = 0;
	auto it = a + left;
             //        for        5  ，       5        
	for (i = left; i < right - 5; i += 5,it+=5)
	{
		sort(it, it + 4, IsBigger);            // 5       
		n = i - left;                          //   i            
		std::swap(a[left + n / 5], a[i+2]);    //                 
		                               //n/5       n/5       
	}                 //                 ， (right-left)/5    
	int num = right - i + 1;
	      //num     5  
	      //      
	if (num > 0)
	{
		sort(it, it + num - 1, IsBigger);       //    
		n = i - left;                           //  
		       //       ，    ，   ，       
		std::swap(a[left + n / 5], a[i + num / 2]); 
	}
	n /= 5;                                     //        
	if (n <= 1)              //       ，       
		return a[left];
	else                     //       ，             
		return Find_mid(a, left, left + n);
}
int Find_pos(int a[], int left, int right,int mid)    
{                                         //           a    
	for (int i=left;i!=right+1;i++)
	{
		if (mid == a[i])
			return i;
	}
}
int Partion(int a[], int left, int right,int pos)   //    ，           
{
	std::swap(a[pos], a[left]);     //           
	int i = left, j = right;
	int pivot = a[left];            //pivot      
	while (i < j)        //      
	{
		while (i < j && a[j] > pivot)    //      pivot  
			j--;
		a[i] = a[j];
		while (i < j && a[i] < pivot)    //      pivot  
			i++;
		a[j] = a[i];
	}
	               //     ，pivot      pivot  ，pivot     pivot  
	a[i] = pivot;                        //  pivot       
	return i;                            // pivot     
}
int BFPTR(int a[], int left, int right, int k)      //BFPTR  
{
	int mid = Find_mid(a, left, right);        //get   
	int pos = Find_pos(a, left, right, mid);   //get      
	int i = Partion(a, left, right, pos);      //get          
	int m = i - left + 1;                      //            m   
	if (k == m)
		return a[i];
	if (k < m)                        //           
		BFPTR(a, left, i - left, k);
	else                              //           
		                                     //       k-m   
		BFPTR(a, i + 1, right, k-m);
}
int main(int argc, char** argv)
{
	int a[N]={ 9,6,3,8,5,2,7,4,1,0 };
	cout << BFPTR(a, 0, 9, 2);
	return 0;
}
  ：1

이 알고리즘 의 최 악의 경우 시간 복잡 도 는 O (n) 이다.