bfprt-线性查找算法-(topK问题)

bfprt-线性查找算法
百度百科: bfprt 
bfprt 流程:
   调用 selectPivot 得到 划分轴.
   调用 partition 按照划分轴进行区间划分(小于划分轴区域,等于划分轴区域,大于划分轴区域),
   根据 k 所在的区域进行处理:
	  在等于区域: 直接返回等于区间任意元素即可.
	  在小于区域: 递归调用 bfprt 处理 小于区域的第k大或小的元素.
	  在大于区域: 递归调用 bfprt 处理 大于区域的第k大或小的元素.

selectPivot 流程:
   数组区域中每5个连续元素成为一组, 最后不足5个元素的也成为一组,
   每组进行组内排序, 并把 每组的中位数 组成中位数数组,
   继续递归调用自身 或 bfprt 处理中位数数组,
   直至中位数数组只有一个元素时返回(即是中位数组的中位数).

partition 流程:
   根据划分轴进行划分: 小于的放左边,等于的放中间,大于的放右边,
   最后返回等于区域的左右边界(闭区间).



创建3个文件：bfprt.h、bfprtArray.c、bfprtArrayTest.c。



bfprtArray.h 
#ifndef BFPRT_H_
#define BFPRT_H_

// 功能: 比较两个数据.
// 参数: a(数据a), b(数据b).
// 返回: a>b返回正数, a<b返回负数, 否则返回0.
// 注意: 其实返回值可以是任意int类型值, 但是为了统一规范使用所以才强制返回值.
typedef int( CompareFunc )( const void *a, const void *b );

// 功能: 数组某一闭区间内的第k小或大的数.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), k(第k小或大), cmp(比较函数).
// 返回: 数组指定区间的第k小或大的元素值.
// 注意: 当 a=NULL 或 cmp=NULL 或 区间范围表示错误 时, 将错误退出程序.
extern int bfprtArray( int32_t a[], int32_t left, int32_t right, int32_t k, CompareFunc *cmp );

#endif

bfprtArray.c 
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "bfprtArray.h"

// 功能: 打印错误信息后就错误退出程序.
// 参数: expression(错误判断表达式), message(需打印的错误信息).
// 返回: 无.
// 注意: 当表达式 expression 为真时, 才触发.
#define ERROR_EXIT( expression, message )                                    
if( (expression) ) {                                                         
	fprintf( stderr, "
error location: file = %s, func = %s, line = %d.
", 
	                       __FILE__, __func__, __LINE__ );                   
	fprintf( stderr, "error  message: %s%s.
a",                            
	                       (message) != NULL ? (message) : __func__,         
		                   (message) != NULL ? "" : " function error" );     
	exit( EXIT_FAILURE );                                                    
}

// 功能: 数组的两个元素进行互换.
// 参数: a(数组首地址), i(数组下标), j(数组下标).
// 返回: 无.
// 注意: 没有副作用的宏, C99标准: #define f ({...}).
#define SWAP( a, i, j ) ({            
	int32_t i1i1i = (i), j1j1j = (j); 
	int32_t t1t1t = *((a) + i1i1i);   
	*((a) + i1i1i) = *((a) + j1j1j);  
	*((a) + j1j1j) = t1t1t;           
})

#define MAX( a, b ) ((a) >= (b) ? (a) : (b))
#define MIN( a, b ) ((a) <= (b) ? (a) : (b))
  • 版本一: 每次 selectPivot 过程动态生成新的中位数数组. 
    // 功能: 数组某一闭区间进行排序.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), cmp(比较函数).
// 返回: 无.
static void insertSort( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, j = 0, t = 0;

	for( int32_t i = left; i <= right; ++i ) {
		t = a[i];
		for( j = i - 1; j >= left && cmp( &t, &a[j] ) < 0; --j ) {
			a[j + 1] = a[j];
		}
		a[j + 1] = t;
	}
}

// 功能: 数组某一闭区间的bfprt划分轴.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), cmp(比较函数).
// 返回: bfprt划分轴.
// 注意: 每5个数为一组进行排序,并得到一个中位数数组,
//       中位数数组继续bfprt算法过程, 直至数组中位数数组大小为1.
static int32_t selectPivot( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t n = right - left + 1;
	int32_t i = 0, sortSize = 0, median = 0;
	int32_t *medianA = NULL, mi = 0;

	if( n == 1 ) {
		return a[left];
	}

	medianA = malloc( sizeof(*medianA) * (n / 5 + MIN( n % 5, 1 )) );

	// 每5个数为一组进行插入排序, 并把每组的上中位数构成一个中位数数组.
	for( i = left; i <= right; i += 5 ) {
		sortSize = MIN( 5, right - i + 1 );
		insertSort( a, i, i + sortSize - 1, cmp );
		medianA[mi++] = a[i + (sortSize - 1) / 2];
	}

	median = mi > 1 ? bfprtArray( medianA, 0, mi - 1, (mi + 1) / 2, cmp ) : medianA[0];
	free( medianA );

	return median;
}

// 功能: 数组某一闭区间按照指定的划分轴进行区间划分.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界),
//       pivot(划分轴), boundary(传入传出参数), cmp(比较函数).
// 返回: 无, 实际是使用了传入传出参数 boundary 进行结果返回.
// 注意: boundary[0] 表示等于区域的左闭边界, boundary[1] 表示等于区域的右闭边界.
static void partition( int32_t a[], int32_t left, int32_t right, int32_t pivot, int32_t boundary[2], CompareFunc *cmp ) {
	int32_t l = left - 1, c = left, r = right + 1;

	while( c < r ) {
		int32_t cmpRes = cmp( &a[c], &pivot );
		if( cmpRes == 0 ) {
			++c;
		} else if( cmpRes < 0 ) {
			SWAP( a, c++, ++l );
		} else {
			SWAP( a, c, --r );
		}
	}
	boundary[0] = l + 1; // 等于区域的左闭边界.
	boundary[1] = r - 1; // 等于区域的右闭边界.
}

// 功能: 数组某一闭区间内的第k小或大的数.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), k(第k小或大).
// 返回: 数组指定区间的第k小或大的元素值.
// 注意: 当 a=NULL 或 cmp=NULL 或 区间范围表示错误 时, 将错误退出程序.
int32_t bfprtArray( int32_t a[], int32_t left, int32_t right, int32_t k, CompareFunc *cmp ) {
	int32_t pivot = 0, boundary[2] = {-1,-1};

	ERROR_EXIT( a == NULL || cmp == NULL, "NullPointerException" );
	ERROR_EXIT( left < 0 || left > right, "IndexOutOfBoundsException" );
	ERROR_EXIT( k < 1, "ParemeterError: k" );

	pivot = selectPivot( a, left, right, cmp );        // 选取划分轴.
	partition( a, left, right, pivot, boundary, cmp ); // 根据划分轴进行区间划分.

	if( k - 1 < boundary[0] ) {
		return bfprtArray( a, left, boundary[0] - 1, k, cmp );
	} else if( k - 1 > boundary[1] ) {
		return bfprtArray( a, boundary[1] + 1, right, k, cmp );
	}

	return a[boundary[0]];
}
  • 版本二: 优化上一版本, 优化掉中位数数组, 并且在 selectPivot 过程中, 不在递归调用bfprt求中位数数组的中位数, 而是递归调用本身. 
    // 功能: 数组某一闭区间进行排序.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), cmp(比较函数).
// 返回: 无.
static void insertSort( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, j = 0, t = 0;

	for( int32_t i = left; i <= right; ++i ) {
		t = a[i];
		for( j = i - 1; j >= left && cmp( &t, &a[j] ) < 0; --j ) {
			a[j + 1] = a[j];
		}
		a[j + 1] = t;
	}
}

// 功能: 数组某一闭区间的bfprt划分轴.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), cmp(比较函数).
// 返回: bfprt划分轴.
// 注意: 每5个数为一组进行排序,并得到一个中位数数组,
//       中位数数组继续bfprt算法过程, 直至数组中位数数组大小为1.
static int32_t selectPivot( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, sortSize = 0, mi = 0;

	if( left == right) {
		return a[left];
	}
	// 每5个数为一组进行排序, 并把每组的上中位数构成一个中位数数组.
	for( i = left; i <= right; i += 5 ) {
		sortSize = MIN( 5, right - i + 1 );
		insertSort( a, i, i + sortSize - 1, cmp );
		// 将每组上中位数交换至数组前部分.
		SWAP( a, left + mi++, i + (sortSize - 1) / 2 );
	}

	return  mi > 1 ? selectPivot( a, left, left + mi - 1, cmp ) : a[left];
}

// 功能: 数组某一闭区间按照指定的划分轴进行区间划分.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界),
//       pivot(划分轴), boundary(传入传出参数), cmp(比较函数).
// 返回: 无, 实际是使用了传入传出参数 boundary 进行结果返回.
// 注意: boundary[0] 表示等于区域的左闭边界, boundary[1] 表示等于区域的右闭边界.
static void partition( int32_t a[], int32_t left, int32_t right, int32_t pivot, int32_t boundary[2], CompareFunc *cmp ) {
	int32_t l = left - 1, c = left, r = right + 1;

	while( c < r ) {
		int32_t cmpRes = cmp( &a[c], &pivot );
		if( cmpRes == 0 ) {
			++c;
		} else if( cmpRes < 0 ) {
			SWAP( a, c++, ++l );
		} else {
			SWAP( a, c, --r );
		}
	}
	boundary[0] = l + 1; // 等于区域的左闭边界.
	boundary[1] = r - 1; // 等于区域的右闭边界.
}

// 功能: 数组某一闭区间内的第k小或大的数.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), k(第k小或大).
// 返回: 数组指定区间的第k小或大的元素值.
// 注意: 当 a=NULL 或 cmp=NULL 或 区间范围表示错误 时, 将错误退出程序.
int32_t bfprtArray( int32_t a[], int32_t left, int32_t right, int32_t k, CompareFunc *cmp ) {
	int32_t pivot = 0, boundary[2] = {-1,-1};

	ERROR_EXIT( a == NULL || cmp == NULL, "NullPointerException" );
	ERROR_EXIT( left < 0 || left > right, "IndexOutOfBoundsException" );
	ERROR_EXIT( k < 1, "ParemeterError: k" );

	pivot = selectPivot( a, left, right, cmp );        // 选取划分轴.
	partition( a, left, right, pivot, boundary, cmp ); // 根据划分轴进行区间划分.

	if( k - 1 < boundary[0] ) {
		return bfprtArray( a, left, boundary[0] - 1, k, cmp );
	} else if( k - 1 > boundary[1] ) {
		return bfprtArray( a, boundary[1] + 1, right, k, cmp );
	}

	return a[boundary[0]];
}
  • 版本三: 优化上一版本, 使 selectPivot 返回下标索引而不是元素值, 而该 partition 过程将会与快排的 partition 一毛一样. 
    // 功能: 数组某一闭区间进行排序.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), cmp(比较函数).
// 返回: 无.
static void insertSort( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, j = 0, t = 0;

	for( int32_t i = left; i <= right; ++i ) {
		t = a[i];
		for( j = i - 1; j >= left && cmp( &t, &a[j] ) < 0; --j ) {
			a[j + 1] = a[j];
		}
		a[j + 1] = t;
	}
}

// 功能: 数组某一闭区间的bfprt划分轴.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), cmp(比较函数).
// 返回: bfprt划分轴.
// 注意: 每5个数为一组进行排序,并得到一个中位数数组,
//       中位数数组继续bfprt算法过程, 直至数组中位数数组大小为1.
static int32_t selectPivot( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, sortSize = 0, mi = 0;

	if( left == right ) {
		return left;
	}
	// 每5个数为一组进行排序, 并把每组的上中位数构成一个中位数数组.
	for( i = left; i <= right; i += 5 ) {
		sortSize = MIN( 5, right - i + 1 );
		insertSort( a, i, i + sortSize - 1, cmp );
		// 将每组上中位数交换至数组前部分.
		SWAP( a, left + mi++, i + (sortSize - 1) / 2 );
	}

	return  mi > 1 ? selectPivot( a, left, left + mi - 1, cmp ) : left;
}

// 功能: 数组某一闭区间按照指定的划分轴进行区间划分.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界),
//       pivot(划分轴), boundary(传入传出参数), cmp(比较函数).
// 返回: 无, 实际是使用了传入传出参数 boundary 进行结果返回.
// 注意: boundary[0] 表示等于区域的左闭边界, boundary[1] 表示等于区域的右闭边界.
static void partition( int32_t a[], int32_t left, int32_t right, int32_t boundary[2], CompareFunc *cmp ) {
	int32_t l = left - 1, c = left, r = right;

	while( c < r ) {
		int32_t cmpRes = cmp( &a[c], &a[right] );
		if( cmpRes == 0 ) {
			++c;
		} else if( cmpRes < 0 ) {
			SWAP( a, c++, ++l );
		} else {
			SWAP( a, c, --r );
		}
	}
	SWAP( a, r, right );
	boundary[0] = l + 1; // 等于区域的左闭边界.
	boundary[1] = r;     // 等于区域的右闭边界.
}

// 功能: 数组某一闭区间内的第k小或大的数.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), k(第k小或大).
// 返回: 数组指定区间的第k小或大的元素值.
// 注意: 当 a=NULL 或 cmp=NULL 或 区间范围表示错误 时, 将错误退出程序.
int32_t bfprtArray( int32_t a[], int32_t left, int32_t right, int32_t k, CompareFunc *cmp ) {
	int32_t pivot = 0, boundary[2] = {-1,-1};

	ERROR_EXIT( a == NULL || cmp == NULL, "NullPointerException" );
	ERROR_EXIT( left < 0 || left > right, "IndexOutOfBoundsException" );
	ERROR_EXIT( k < 1, "ParemeterError: k" );

	pivot = selectPivot( a, left, right, cmp ); // 选取划分轴.
	SWAP( a, pivot, right );                    // 划分轴位置与最后位置进行交换.
	partition( a, left, right, boundary, cmp ); // 根据划分轴进行区间划分.

	if( k - 1 < boundary[0] ) {
		return bfprtArray( a, left, boundary[0] - 1, k, cmp );
	} else if( k - 1 > boundary[1] ) {
		return bfprtArray( a, boundary[1] + 1, right, k, cmp );
	}

	return a[boundary[0]];
}
  • 版本四: 修改上一版本, 使 insertSort 返回排序区间中位数的下标索引, 而 selectPivot 不必递归处理直至中位数数组只有一个元素, 而是当不多于5个元素时,直接排序返回. 
    // 功能: 数组某一闭区间进行排序.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), cmp(比较函数).
// 返回: 无.
static int32_t insertSort( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, j = 0, t = 0;

	for( int32_t i = left; i <= right; ++i ) {
		t = a[i];
		for( j = i - 1; j >= left && cmp( &t, &a[j] ) < 0; --j ) {
			a[j + 1] = a[j];
		}
		a[j + 1] = t;
	}

	return left + (right - left) / 2;
}

// 功能: 数组某一闭区间的bfprt划分轴.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), cmp(比较函数).
// 返回: bfprt划分轴.
// 注意: 每5个数为一组进行排序,并得到一个中位数数组,
//       中位数数组继续bfprt算法过程, 直至数组中位数数组大小为1.
static int32_t selectPivot( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, sortSize = 0, mi = 0;

	if( right - left + 1 <= 5 ) {
		return insertSort( a, left, right, cmp );
	}
	// 每5个数为一组进行排序, 并把每组的上中位数构成一个中位数数组.
	for( i = left; i <= right; i += 5 ) {
		sortSize = MIN( 5, right - i + 1 );
		insertSort( a, i, i + sortSize - 1, cmp );
		// 将每组上中位数交换至数组前部分.
		SWAP( a, left + mi++, i + (sortSize - 1) / 2 );
	}
	if( mi <= 5 ) {
		return insertSort( a, left, left + mi - 1, cmp );
	}

	return selectPivot( a, left, left + mi - 1, cmp );
}

// 功能: 数组某一闭区间按照指定的划分轴进行区间划分.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界),
//       pivot(划分轴), boundary(传入传出参数), cmp(比较函数).
// 返回: 无, 实际是使用了传入传出参数 boundary 进行结果返回.
// 注意: boundary[0] 表示等于区域的左闭边界, boundary[1] 表示等于区域的右闭边界.
static void partition( int32_t a[], int32_t left, int32_t right, int32_t boundary[2], CompareFunc *cmp ) {
	int32_t l = left - 1, c = left, r = right;

	while( c < r ) {
		int32_t cmpRes = cmp( &a[c], &a[right] );
		if( cmpRes == 0 ) {
			++c;
		} else if( cmpRes < 0 ) {
			SWAP( a, c++, ++l );
		} else {
			SWAP( a, c, --r );
		}
	}
	SWAP( a, r, right );
	boundary[0] = l + 1; // 等于区域的左闭边界.
	boundary[1] = r;     // 等于区域的右闭边界.
}

// 功能: 数组某一闭区间内的第k小或大的数.
// 参数: a(数组首地址), left(左闭边界), right(右闭边界), k(第k小或大).
// 返回: 数组指定区间的第k小或大的元素值.
// 注意: 当 a=NULL 或 cmp=NULL 或 区间范围表示错误 时, 将错误退出程序.
int32_t bfprtArray( int32_t a[], int32_t left, int32_t right, int32_t k, CompareFunc *cmp ) {
	int32_t pivot = 0, boundary[2] = {-1,-1};

	ERROR_EXIT( a == NULL || cmp == NULL, "NullPointerException" );
	ERROR_EXIT( left < 0 || left > right, "IndexOutOfBoundsException" );
	ERROR_EXIT( k < 1, "ParemeterError: k" );

	pivot = selectPivot( a, left, right, cmp ); // 选取划分轴.
	SWAP( a, pivot, right );                    // 划分轴位置与最后位置进行交换.
	partition( a, left, right, boundary, cmp ); // 根据划分轴进行区间划分.

	if( k - 1 < boundary[0] ) {
		return bfprtArray( a, left, boundary[0] - 1, k, cmp );
	} else if( k - 1 > boundary[1] ) {
		return bfprtArray( a, boundary[1] + 1, right, k, cmp );
	}

	return a[boundary[0]];
}

bfprtArrayTest.c 
实现对数器.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include "bfprtArray.c"


#define MAX( a, b ) ((a) >= (b) ? (a) : (b))


// 功能: 对数组的某一区间内的元素值进行随机化.
// 参数: a(数组首地址), left(左闭区间), right(右闭区间), v(最大随机值).
// 返回: 无.
// 注意: 当v是正数/负数/零时,随机值的区间分别为[-v, v]/[]/[].
static void randomArray( int32_t a[], int32_t left, int32_t right, int32_t v ) {
	v -= v != INT32_MAX ? 0 : 1;
	while( left <= right ) {
		a[left++] = rand() % (v + 1) - rand() % (v + 1);
	}
}

// 功能: 将源数组的某一区间内的元素值拷贝至目的数组中.
// 参数: a(源数组首地址), left(左闭区间), right(右闭区间), b(目的数组首地址).
// 返回: 无.
// 注意: 无.
static void cloneArray( const int32_t a[], int32_t left, int32_t right, int32_t b[] ) {
	while( left <= right ) {
		b[left] = a[left];
		++left;
	}
}

// 功能: 将数组的某一区间内的元素值送入到文件流中.
// 参数: a(数组首地址), left(左闭区间), right(右闭区间), fp(文件流指针).
// 返回: 无.
// 注意: 无.
static void printArray( const int32_t a[], int32_t left, int32_t right, FILE *fp ) {
	fprintf( fp, "[" );
	while( left <= right ) {
		fprintf( fp, "%5d%s", a[left], left != right ? ", " : "" );
		++left;
	}
	fprintf( fp, "]
" );
}

// 功能: 数据比较.
// 参数: a(数据1), b(数据2).
// 返回: a<b返回负数, a>b返回正数, 否则返回0.
// 注意: 无.
static int cmp( const void *a, const void *b ) {
	#if 1
	return *(int32_t *) a - *(int32_t *) b;
	#else
	return *(int32_t *) b - *(int32_t *) a;
	#endif
}

// 功能: 绝对正确的方法.
// 参数: a(数组首地址), left(左闭区间), right(右闭区间).
// 返回: 无.
// 注意: 使用稳定的库函数方法 或 非常笨的方法(如暴力循环,暴力递归搜索).
static int correct( int32_t a[], int32_t left, int32_t right, int32_t k ) {
	qsort( &a[left], right - left + 1, sizeof(*a), cmp );

	return a[k - 1];
}

// 功能: 待测试的方法.
// 参数: a(数组首地址), left(左闭区间), right(右闭区间).
// 返回: 无.
// 注意: 使用技巧性的高效的正确性未知的方法.
static int test( int32_t a[], int32_t left, int32_t right, int32_t k ) {
	return bfprtArray( a, left, right, k, cmp );
}

int main( int argc, char *argv[] ) {
	const int32_t times = 7654321; // 测试的总测试.
	const int32_t maxSize = 123;   // 随机的最大长度.
	int32_t size = 0, left = 0, right = 0;
	int32_t *a = NULL, *t = NULL, *c = NULL;
	int32_t i = 0;

	srand( time( NULL ) );
	a = malloc( sizeof(*a) * maxSize );
	c = malloc( sizeof(*c) * maxSize );
	t = malloc( sizeof(*t) * maxSize );

	for( i = 0; i < times; ++i ) {
		size = rand() % maxSize + 1; // 随机化数组长度, 取值区间(0,maxSize].

		randomArray( a, 0, size - 1, 321 );
		cloneArray( a, 0, size - 1, c );
		cloneArray( a, 0, size - 1, t );

		left = 0;
		right = size - 1;

		int k = rand() % size + 1; // 取值区间(0,size].

		int cr = correct( c, left, right, k ); // 绝对正确的方法.
		int tr = test( t, left, right, k );    // 待测试的方法.
		if( cr != tr ) {
			fprintf( stderr, "source  :" );
			printArray( a, 0, size - 1, stderr );
			fprintf( stderr, "correct : %d
", cr );
			fprintf( stderr, "test    : %d
", tr );
			fprintf( stderr, " 本次测试不通过!
a" );
			exit( EXIT_FAILURE );
		}
	}

	free( t );
	free( c );
	free( a );

	printf( "总共 %d 次测试且全部通过!
", times );

	return EXIT_SUCCESS;
}

bfprtArrayTest.sh 
# !/bin/bash

for(( i = 1; i <= 21; ++i )) do
	printf "%02d" ${i}
	echo -n ______________
	./bfprtTest
done

参考: https://my.oschina.net/dfbb/blog/393346
参考: https://en.academic.ru/dic.nsf/enwiki/301561

重点参考人物: 左神.



【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/hujunxiang98/p/12925173.html